#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; 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] > 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_maxchild(int x){ while(ismaxchild[x]) x = hld.parent(x); return 0; } void set_A(int p, int a){ int parent = hld.parent(p); 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; maxchild[parent] = children[parent].begin() -> second; ismaxchild[maxchild[parent]] = 1; int updv = ruq::query(hld.idxs()[maxchild[parent]]); int updr = solve_maxchild(parent); //cout << " updr = " << updr << endl; for(auto path : hld.path(updr, parent)) ruq::apply(path.first, path.second, updv); } } int query(int u, int v){ int au = A[u]; int av = A[v]; set_A(u, av); set_A(v, au); //cout << "u = " << u << ", v = " << v << endl; int g = solve_parentmax(u); //cout << "g = " << g << endl; int ans = g; if(u != g){ if(children[g].size() <= 1) g = -1; else if(hld.lca(u, maxchild[g]) == maxchild[g]){ auto i = children[g].begin(); i++; g = i -> second; } else g = maxchild[g]; } //if(g != -1) ans = ruq::query(hld.idxs()[g]); if(g != -1){ ans = g; while(maxchild[ans] != -1) ans = maxchild[ans]; } //cout << "ans = " << ans << endl; return ans; } 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); } //cout << "##" << endl; 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); 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]; } //cout << "initialized " << endl; //cout << " ismaxchild = ["; for(auto a : ismaxchild) cout << " " << a; cout << " ]" << endl; //cout << " isparentparentmax = ["; rep(i,N) cout << " " << isparentparentmax_rq.get(hld.idxs()[i]); cout << " ]" << endl; //cout << " heavy child = ["; rep(i,N) cout << " " << hld.heavy_path_child(i) << flush; cout << " ]" << endl; //cout << " parent = ["; rep(i,N) cout << " " << hld.parent(i) << flush; cout << " ]" << endl; 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;