木の直径に関する問題． 木の最長パスの一つを直径といい，これはDFSを2回することで求まる． まず任意の点 \(v\) からDFSをして，一番遠かった点を \(a\) とする． 次に \(a\) からDFSをして，一番遠かった点を \(b\) とする． \(a,b\) のパスが直径になる．
また， \(a,b\) のパスの中心を \(c\) とおけば， 任意の頂点 \(x\) からの最長パスは， \(x,a\) のパス，または \(x,b\) のパスになる． 実際には， \(a,b\)のうち\(x\)から見て \(c\)と反対にある方が選ばれる．
実装
クエリ先読みしておけば， \(a,b\) からDFSするときに距離が求まる． 先読みするときは， \(qs_{v} = \) ( 頂点\(v\) に対する(クエリ番号，距離 \(k\) )のペア ) の形で保持する．
別解
ダブリングで距離を求めれば，先読みは不要．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n; cin >> n;
vvll to(n);
rep(i,n-1){
ll a,b; cin >> a >> b;
--a,--b;
to[a].push_back(b);
to[b].push_back(a);
}
ll q; cin >> q;
rep(qi,q){
ll v,k ; cin >> v >> k;
--v;
qs[v].emplace_back(qi, k);
}
vll ans(q, -1);
deque<ll> vs;
pll ret = {-1, -1};
chmax(ret, {d, cu});
vs.push_front(cu);
for(auto [qi,k]: qs[cu]){
if(k < vs.size()){
ans[qi] = vs[k]+1;
}
}
chmax(ret, dfs(dfs, ne, cu, d+1));
}
vs.pop_front();
return ret;
};
ll a = dfs(dfs, 0).second;
ll b = dfs(dfs, a).second;
ans = vll(q, -1);
vs = deque<ll>();
dfs(dfs, a);
vs = deque<ll>();
dfs(dfs, b);
rep(qi,q){
cout << ans[qi] << endl;
}
return 0;
}
