「解题报告」[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;
	}
}