#include #include #include #include using namespace std; struct heavy_light_decomposition{ private: int N; vector P; vector PP; vector PD; vector D; vector I; vector rangeL; vector rangeR; public: heavy_light_decomposition(const vector>& E = {{}}){ N = E.size(); P.assign(N, -1); I = {0}; I.reserve(N); for(int i=0; i Z(N, 1); vector nx(N, -1); PP.resize(N); for(int i=0; i=1; i--){ int p = I[i]; Z[P[p]] += Z[p]; if(nx[P[p]] == -1) nx[P[p]] = p; if(Z[nx[P[p]]] < Z[p]) nx[P[p]] = p; } for(int p : I) if(nx[p] != -1) PP[nx[p]] = p; PD.assign(N,N); PD[0] = 0; D.assign(N,0); for(int p : I) if(p != 0){ PP[p] = PP[PP[p]]; PD[p] = min(PD[PP[p]], PD[P[p]]+1); D[p] = D[P[p]]+1; } rangeL.assign(N,0); rangeR.assign(N,0); vector dfs; dfs.push_back(0); while(dfs.size()){ int p = dfs.back(); rangeR[p] = rangeL[p] + Z[p]; int ir = rangeR[p]; dfs.pop_back(); for(int e : E[p]) if(P[p] != e) if(e != nx[p]){ rangeL[e] = (ir -= Z[e]); dfs.push_back(e); } if(nx[p] != -1){ rangeL[nx[p]] = rangeL[p] + 1; dfs.push_back(nx[p]); } } I.resize(N); for(int i=0; i PD[v]) u = P[PP[u]]; while(PP[u] != PP[v]){ u = P[PP[u]]; v = P[PP[v]]; } return (D[u] > D[v]) ? v : u; } int dist(int u, int v) const { return depth(u) + depth(v) - depth(lca(u,v)) * 2; } vector> path(int r, int c, bool include_root = true, bool reverse_path = false) const { vector> res; while(PD[r] < PD[c]){ res.push_back({ rangeL[PP[c]], rangeL[c]+1 }); c = P[PP[c]]; } if(PP[r] != PP[c]) return {}; if(D[r] > D[c]) return {}; res.push_back({ rangeL[r], rangeL[c]+1 }); if(!include_root){ res.back().first++; if(res.back().first == res.back().second) res.pop_back(); } if(!reverse_path) reverse(res.begin(),res.end()); return res; } const vector& idxs() const { return rangeL; } const vector& invidxs() const { return I; } int meet(int x, int y, int z) const { return lca(x,y) ^ lca(y,z) ^ lca(x,z); } int jump(int from, int to, int d) const { int g = lca(from,to); int dist0 = D[from] - D[g] * 2 + D[to]; if(dist0 > d) return -1; int p = from; if(D[from] - D[g] > d){ p = to; d = dist0 - d; } while(D[p] - D[PP[p]] > d){ d -= D[p] - D[PP[p]] + 1; p = P[PP[p]]; } return I[rangeL[p] - d]; } int heavy_path_child(int p){ int ip = rangeL[p]; if(ip == N-1) return -1; int cand = I[ip + 1]; if(PP[cand] != PP[p]) return -1; return cand; } int parent(int p){ return P[p]; } }; #include #include #include #include #include #include using namespace std; #define rep(i,n) for(int i=0; i<(n); i++) namespace ruq { map rq; void init(){ rq[-1] = 0; } int query(int p){ auto i = rq.upper_bound(p); i--; return i->second; } void apply(int l, int r, int updval){ if(l >= r) return; int lastval = query(l); auto i = rq.lower_bound(l); while(true){ if(i == rq.end()) break; if(r < i->first) break; lastval = i->second; i = rq.erase(i); } rq.insert(make_pair(l, updval)); rq.insert(make_pair(r, lastval)); } } int N; vector A; vector> E; heavy_light_decomposition hld; vector, greater>>> children; vector maxchild; vector ismaxchild; namespace all_is_good_query{ using S = int; S op(S l, S r){ return l & r; } S e(){ return 1; } using rq = atcoder::segtree; bool check(S x){ return x; } } all_is_good_query::rq isparentparentmax_rq; all_is_good_query::rq ismaxchild_rq; int is_parent_max(int p){ if(p == 0) return 0; if(maxchild[p] < 0) return 1; return (A[hld.parent(p)] > A[maxchild[p]]) ? 1 : 0; } int is_parent_parent_max(int p){ if(hld.depth(p) < 2) return 0; int pp = hld.parent(p); int ppp = hld.parent(pp); if(children[pp].size() <= 1) return 1; if(maxchild[pp] != p) return (A[ppp] > A[maxchild[pp]]) ? 1 : 0; auto i = children[pp].begin(); i++; return (A[ppp] > A[i->second]) ? 1 : 0; } int solve_parentmax(int x){ if(x == 0) return x; if(is_parent_max(x) == 0) return x; while(is_parent_parent_max(x)) x = hld.parent(x); if(x != 0) x = hld.parent(x); return x; } /* int solve_parentmax(int x){ if(x == 0) return x; if(is_parent_max(x) == 0) return x; auto path = hld.path(0,x); while(!path.empty()){ auto p = path.back(); path.pop_back(); int l = isparentparentmax_rq.min_left(p.second, all_is_good_query::check); l = min(max(l, p.first + 2), p.second); if(p.first + 2 < l){ return hld.invidxs()[l-2]; } while(l != p.first){ l--; int pathp = hld.invidxs()[l]; if(is_parent_parent_max(pathp)) continue; return hld.parent(hld.invidxs()[l]); } } return 0; } */ int solve_maxchild(int x){ auto path = hld.path(0,x); while(!path.empty()){ auto p = path.back(); path.pop_back(); int l = ismaxchild_rq.min_left(p.second, all_is_good_query::check); if(p.first + 1 < l){ return hld.invidxs()[l-1]; } int pathp = hld.invidxs()[p.first]; if(!ismaxchild[pathp]) return pathp; } return 0; } vector dp; void set_A(int p, int a){ int heavy_child = hld.heavy_path_child(p); int parent = hld.parent(p); int heavy_child2 = -1; if(heavy_child != -1) heavy_child2 = hld.heavy_path_child(heavy_child); if(parent != -1){ children[parent].erase(make_pair(A[p], p)); } A[p] = a; if(parent != -1){ children[parent].insert(make_pair(A[p], p)); ismaxchild[maxchild[parent]] = 0; ismaxchild_rq.set(hld.idxs()[maxchild[parent]], 0); maxchild[parent] = children[parent].begin() -> second; ismaxchild[maxchild[parent]] = 1; ismaxchild_rq.set(hld.idxs()[maxchild[parent]], 1); int updv = ruq::query(hld.idxs()[maxchild[parent]]); int updr = solve_maxchild(parent); //for(auto path : hld.path(updr, parent)) ruq::apply(path.first, path.second, updv); int c = parent; while(ismaxchild[c]){ dp[c] = updv; c = hld.parent(c); } dp[c] = updv; } if(heavy_child2 != -1) isparentparentmax_rq.set(hld.idxs()[heavy_child2], is_parent_parent_max(heavy_child2)); isparentparentmax_rq.set(hld.idxs()[p], is_parent_parent_max(p)); } int query(int u, int v){ int au = A[u]; int av = A[v]; set_A(u, av); set_A(v, au); int g = solve_parentmax(u); if(u != g){ if(children[g].size() <= 1) return g; else if(hld.lca(u, maxchild[g]) == maxchild[g]){ auto i = children[g].begin(); i++; g = i -> second; } } // g = ruq::query(hld.idxs()[g]); g = dp[g]; return g; } int main(void){ cin >> N; A.resize(N); rep(i,N) A[i] = i; E.resize(N); rep(i,N-1){ int u,v; cin >> u >> v; u--; v--; E[u].push_back(v); E[v].push_back(u); } hld = heavy_light_decomposition(E); E.clear(); E.resize(N); children.resize(N); for(int i=1; i second; ismaxchild.assign(N,0); for(int i=1; i> Q; if(10000000 / N <= Q) return 1; ruq::init(); { //vector dp(N); dp.resize(N); rep(i,N) dp[i] = i; for(int i=N-1; i>=0; i--){ int p = hld.invidxs()[i]; if(children[p].empty()) continue; dp[p] = dp[maxchild[p]]; } rep(p,N) ruq::rq[hld.idxs()[p]] = dp[p]; } rep(queryid, Q){ int u,v; cin >> u >> v; u = (u+N-1+prevans) % N + 1; v = (v+N-1+prevans) % N + 1; u--; v--; int ans = query(u,v) + 1; cout << ans << "\n"; prevans = ans; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;