「解题报告」[ABC267F] Exactly K Steps
大家好，我是个毒瘤，我非常喜欢没脑子做法，于是我就用点分治过了这个题 .
离线在每个点存下与其相关的询问 . 考虑如何计算跨重心的答案 .
记录下每个点在当前重心下的深度，同时开一个桶 \(t_{k, 0/1}\) 存下当前深度为 \(k\) 的，来自重心的不同子树的两个点 .
把记录深度的搜索过程中遇到的询问拿出来，在记录完桶之后处理 . 具体的，对于一个询问 \((u, k)\)，查找桶 \(t_{k - dep_u,0/1}\) 内是否有与 \(u\) 不在同一棵子树的点 . 需要特殊处理一下 \(k-dep_u = 0\) 的询问 .
具体实现细节可以看代码 .
询问虽然不是一次性全能处理完的，但是由于点分治最多递归 \(\log n\) 层，每个询问也最多只会被取出 \(\log n\) 次，时间复杂度是 \(O((n+q)\log n)\) .
Code：
const int N = 2e5 + 10, P = 998244353;
namespace SOLVE {
int n, q, ans[N];
std::vector <int> tu[N];
std::vector <pii> qu[N];
inline int rnt () {
int x = 0, w = 1; char c = getchar ();
while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
return x * w;
}
int root, sz[N], tmp[N][2][2], mx[N];
bool vis[N];
class T {
public:
int u, d, r;
T () = default;
T (int _u, int _d, int _r): u(_u), d(_d), r(_r) {}
};
std::queue <T> qa;
void DFS_Find (int u, int fa, int dep, int r) {
if (!qu[u].empty ()) qa.push (T (u, dep, r));
if (!tmp[dep][0][0]) tmp[dep][0][0] = u, tmp[dep][0][1] = r;
else if (!tmp[dep][1][0] && tmp[dep][0][1] != r) tmp[dep][1][0] = u, tmp[dep][1][1] = r;
far (v, tu[u]) {
if (vis[v] || v == fa) continue;
DFS_Find (v, u, dep + 1, r);
}
return;
}
int DFS_MaxDep (int u, int fa, int dep) {
int mx = dep;
far (v, tu[u]) if (!vis[v] && v != fa)
mx = std::max (mx, DFS_MaxDep (v, u, dep + 1));
return mx;
}
inline void Calc (int u) {
far (v, tu[u]) {
if (vis[v]) continue;
DFS_Find (v, u, 1, v);
}
if (!qu[u].empty ()) qa.push (T (u, 0, u));
while (!qa.empty ()) {
T f = qa.front (); qa.pop ();
far (p, qu[f.u]) {
if (ans[p.second]) continue;
int d = p.first - f.d;
if (d < 0) continue;
else if (d == 0) ans[p.second] = u;
else {
if (f.r == tmp[d][0][1]) ans[p.second] = tmp[d][1][0];
else ans[p.second] = tmp[d][0][0];
}
}
}
int mxd = DFS_MaxDep (u, 0, 0);
_for (i, 0, mxd) tmp[i][0][0] = tmp[i][0][1] = tmp[i][1][0] = tmp[i][1][1] = 0;
return;
}
void GetRoot (int u, int fa) {
mx[u] = 0, sz[u] = 1;
far (v, tu[u]) {
if (vis[v] || v == fa) continue;
GetRoot (v, u), sz[u] += sz[v];
mx[u] = std::max (mx[u], sz[v]);
}
mx[u] = std::max (mx[u], sz[0] - sz[u]);
if (mx[root] > mx[u]) root = u;
return;
}
void GetSize (int u, int fa) {
sz[u] = 1;
far (v, tu[u]) {
if (vis[v] || v == fa) continue;
GetSize (v, u), sz[u] += sz[v];
}
return;
}
void Divide (int u) {
Calc (u), vis[u] = true;
far (v, tu[u]) {
if (vis[v]) continue;
sz[0] = sz[v], mx[root = 0] = N;
GetRoot (v, u), GetSize (root, u);
Divide (root);
}
return;
}
inline void In () {
n = rnt ();
_for (i, 1, n - 1) {
int u = rnt (), v = rnt ();
tu[u].emplace_back (v);
tu[v].emplace_back (u);
}
q = rnt ();
_for (i, 1, q) {
int u = rnt (), d = rnt ();
qu[u].emplace_back (d, i);
}
return;
}
inline void Solve () {
root = 0, sz[0] = n, mx[0] = N;
GetRoot (1, 0), GetSize (root, 0);
Divide (root);
return;
}
inline void Out () {
_for (i, 1, q) printf ("%d\n", ans[i] ? ans[i] : -1);
return;
}
}