(accoders::NOI #5541. 醉(intoxicated)）
题目描述
Robin 有一棵树，他有 \(m\) 次询问，每次询问他给你 \(u,k\)，你需要输出树上的一个节点 \(v\) 满足 \(dist(u,v)=k\)，或者报告无解。
\(dist(u,v)\) 表示树上 \(u\) 到 \(v\) 的最短路径的边数。\(n\leq 10^5\)
solution
考虑求出每个点能到达的最远点，如果 \(k\) 超出这个范围则必然无解，否则在它到最远点的路径上任意截取 \(k\) 条边，取出向最远点走 \(k\) 条边到达的点。
使用换根 DP 求出最远点，使用倍增 LCA 求出树上 \(k\) 级祖先（查询一条链上走 \(k\) 步等价于从某个端点向上跳祖先）。\(O(n\log n)\)。
或是你发现这个所谓的最远点一定是直径两端点之一。于是随便拉一条直径，离线询问，以两端分别为根 dfs，同时维护一个祖先的栈。查询 \(k\) 级祖先就是看看栈中前 \(k\) 个访问到的祖先。
code
点击查看代码
// ubsan: undefined
// accoders
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
int n, ans[1 << 18], Q;
vector<int> g[1 << 18];
vector<pair<int, int>> qry[1 << 18];
int stk[1 << 18], top = 0, hei[1 << 18];
int dfs(int u, int fa) {
stk[++top] = u;
for (auto q : qry[u]) {
if (q.first < top)
ans[q.second] = stk[top - q.first];
}
hei[u] = 0;
int res = u;
for (int v : g[u])
if (v != fa) {
int ret = dfs(v, u);
if (hei[v] + 1 > hei[u])
hei[u] = hei[v] + 1, res = ret;
}
--top;
return res;
}
int main() {
freopen("intoxicated.in", "r", stdin);
freopen("intoxicated.out", "w", stdout);
scanf("%d", &n);
for (int i = 1, u, v; i < n; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
scanf("%d", &Q);
for (int i = 1, u, d; i <= Q; i++) {
scanf("%d%d", &u, &d);
qry[u].emplace_back(d, i);
}
memset(ans, -1, sizeof ans);
hei[0] = 0;
dfs(dfs(dfs(1, 0), 0), 0);
for (int i = 1; i <= Q; i++) printf("%d\n", ans[i]);
return 0;
}