#include #include #include #include #include #include #include using namespace std; template struct Tree{ vector> E, par0; vector dist0; S N, log=0; Tree (const vector> &_E){ N = _E.size(); E = _E; } //fromを根とする木の各頂点の深さを求める vector depth (S from) { vector dist(N); _depth(from, -1, dist); return dist; } vector org (S from) { vector dist(N); _org(from, 1e9, dist); return dist; } S _org (S from, S p, vector &dist) { S mi = 1e9; for (auto to : E[from]){ if (to == p) continue; mi = min(mi, _org(to, from, dist)+1); } if (mi == 1e9) mi = 0; return dist[from] = mi; } void _depth(S from, S p, vector &dist) { for (auto to : E[from]){ if (to == p) continue; dist[to] = dist[from]+1; _depth(to, from, dist); } } //木の二頂点(a, b)間の最短距離を求める S dist(S a, S b){ S c = lca(a, b); return dist0[a] + dist0[b]- 2*dist0[c]; } //木の二頂点(a, b)のLCAを求める S lca(S a, S b){ if (par0.size() == 0){ dist0 = depth(0); _doubling(); } if (dist0[a] < dist0[b]) swap(a, b); for (S i=0; i<=log; i++){ if ((dist0[a]-dist0[b]) & (1LL<=0; i--){ if (par0[i][a] != par0[i][b]){ a = par0[i][a]; b = par0[i][b]; } } return par0[0][a]; } void _doubling(){ S cnt = 1; while(cnt < N){ cnt *= 2; log++; } par0.resize(log+1, vector(N)); _ancestor(0, -1); for (S i=1; i<=log; i++){ for (S j=0; j shortest_path(S from, S goal) const{ vector path, pt; _shortest_path(from, goal, -1, pt, path); return path; } void _shortest_path(S from, S goal, S p, vector &pt, vector &path) const{ pt.push_back(from); if (from == goal) path = pt; for (auto to : E[from]){ if (to == p) continue; _shortest_path(to, goal, from, pt, path); } pt.pop_back(); } //木の直径とその両端の点を求める tuple diameter() const{ S s=0, t=0, mx=0; _diameter(s, -1, 0, mx, t); s=t; t=0; mx=0; _diameter(s, -1, 0, mx, t); return make_tuple(s, t, mx); } void _diameter(S from, S p, S d, S &mx, S &argmx) const{ if (d > mx){ argmx = from; mx = d; } for (auto to : E[from]){ if (to == p) continue; _diameter(to, from, d+1, mx, argmx); } } //fromを根とする木の部分木のサイズを求める vector subtree_size(S from) const{ vector subtree(N); _subtree_size(from, -1, subtree); return subtree; } S _subtree_size(S from, S p, vector &subtree) const{ S cnt = 1; for (auto to : E[from]){ if (to == p) continue; cnt += _subtree_size(to, from, subtree); } return subtree[from] = cnt; } }; int main(){ long long N, A, B, Q; cin >> N; vector> E(N); for (int i=0; i < N-1; i++){ cin >> A >> B; A--; B--; E[A].push_back(B); E[B].push_back(A); } Tree tree(E); vector leaf, root; leaf = tree.org(0); root = tree.depth(0); for (int i=0; i