//#define _GLIBCXX_DEBUG //#pragma GCC target("avx2") //#pragma GCC optimize("O3") //#pragma GCC optimize("unroll-loops") #include using namespace std; #ifdef LOCAL #include #define OUT(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define OUT(...) (static_cast(0)) #endif #define endl '\n' #define lfs cout<= (ll)(n); i--) using ll = long long; using ld = long double; const ll MOD1 = 1e9+7; const ll MOD9 = 998244353; const ll INF = 1e18; using P = pair; template using PQ = priority_queue; template using QP = priority_queue,greater>; templatebool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;} templatebool chmax(T1 &a,T2 b){if(avoid ans(bool x,T1 y,T2 z){if(x)cout<void anss(T1 x,T2 y,T3 z){ans(x!=y,x,z);}; templatevoid debug(const T &v,ll h,ll w,string sv=" "){for(ll i=0;ivoid debug(const T &v,ll n,string sv=" "){if(n!=0)cout<void debug(const vector&v){debug(v,v.size());} templatevoid debug(const vector>&v){for(auto &vv:v)debug(vv,vv.size());} templatevoid debug(stack st){while(!st.empty()){cout<void debug(queue st){while(!st.empty()){cout<void debug(deque st){while(!st.empty()){cout<void debug(PQ st){while(!st.empty()){cout<void debug(QP st){while(!st.empty()){cout<void debug(const set&v){for(auto z:v)cout<void debug(const multiset&v){for(auto z:v)cout<void debug(const array &a){for(auto z:a)cout<void debug(const map&v){for(auto z:v)cout<<"["<vector>vec(ll x, ll y, T w){vector>v(x,vector(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} vectordx={1,-1,0,0,1,1,-1,-1};vectordy={0,0,1,-1,1,-1,1,-1}; templatevector make_v(size_t a,T b){return vector(a,b);} templateauto make_v(size_t a,Ts... ts){return vector(a,make_v(ts...));} templateostream &operator<<(ostream &os, const pair&p){return os << "(" << p.first << "," << p.second << ")";} templateostream &operator<<(ostream &os, const vector &v){os<<"[";for(auto &z:v)os << z << ",";os<<"]"; return os;} templatevoid rearrange(vector&ord, vector&v){ auto tmp = v; for(int i=0;ivoid rearrange(vector&ord,Head&& head, Tail&&... tail){ rearrange(ord, head); rearrange(ord, tail...); } template vector ascend(const vector&v){ vectorord(v.size());iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],i) vector descend(const vector&v){ vectorord(v.size());iota(ord.begin(),ord.end(),0); sort(ord.begin(),ord.end(),[&](int i,int j){return make_pair(v[i],-i)>make_pair(v[j],-j);}); return ord; } template vector inv_perm(const vector&ord){ vectorinv(ord.size()); for(int i=0;i0);return n>=0?n/div:(n-div+1)/div;} ll CEIL(ll n,ll div){assert(div>0);return n>=0?(n+div-1)/div:n/div;} ll digitsum(ll n){ll ret=0;while(n){ret+=n%10;n/=10;}return ret;} ll modulo(ll n,ll d){return (n%d+d)%d;}; templateT min(const vector&v){return *min_element(v.begin(),v.end());} templateT max(const vector&v){return *max_element(v.begin(),v.end());} templateT acc(const vector&v){return accumulate(v.begin(),v.end(),T(0));}; templateT reverse(const T &v){return T(v.rbegin(),v.rend());}; //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count()); int popcount(ll x){return __builtin_popcountll(x);}; int poplow(ll x){return __builtin_ctzll(x);}; int pophigh(ll x){return 63 - __builtin_clzll(x);}; templateT poll(queue &q){auto ret=q.front();q.pop();return ret;}; templateT poll(priority_queue &q){auto ret=q.top();q.pop();return ret;}; templateT poll(QP &q){auto ret=q.top();q.pop();return ret;}; templateT poll(stack &s){auto ret=s.top();s.pop();return ret;}; ll MULT(ll x,ll y){if(LLONG_MAX/x<=y)return LLONG_MAX;return x*y;} ll POW2(ll x, ll k){ll ret=1,mul=x;while(k){if(mul==LLONG_MAX)return LLONG_MAX;if(k&1)ret=MULT(ret,mul);mul=MULT(mul,mul);k>>=1;}return ret;} ll POW(ll x, ll k){ll ret=1;for(int i=0;i struct edge { int to; T cost; int id; edge():to(-1),id(-1){}; edge(int to, T cost = 1, int id = -1):to(to), cost(cost), id(id){} operator int() const { return to; } }; template using Graph = vector>>; template Graphrevgraph(const Graph &g){ Graphret(g.size()); for(int i=0;i Graph readGraph(int n,int m,int indexed=1,bool directed=false,bool weighted=false){ Graph ret(n); for(int es = 0; es < m; es++){ int u,v; T w=1; cin>>u>>v;u-=indexed,v-=indexed; if(weighted)cin>>w; ret[u].emplace_back(v,w,es); if(!directed)ret[v].emplace_back(u,w,es); } return ret; } template Graph readParent(int n,int indexed=1,bool directed=true){ Graphret(n); for(int i=1;i>p; p-=indexed; ret[p].emplace_back(i); if(!directed)ret[i].emplace_back(p); } return ret; } template struct HLD{ using D=long long; int n; vectorsz;//部分木サイズ vectordep; vectorpar; vectorhead; Graph &g;//隣接リスト vector>edges;//データ構造に乗せるedge列 vectorin,out;//[in,out)で部分木、[ina,inb]でa~bのパス(aが上) vectorcomp;//連結成分の根 //inは頂点のindexを表す。また、edge列の下側の頂点である HLD(Graph &g,int r=-1):g(g),n(g.size()){ hld_build(r); } void hld_build(int root = -1){ in.assign(n,-1);out.assign(n,-1);dep.assign(n,0); par.assign(n,-1);head.assign(n,-1);sz.assign(n,-1);comp.assign(n,-1); edges.assign(n,edge()); if(root == -1){//根がどこでも良い場合(森でも可) for(int i=0;i sz[g[k][0].to])swap(e, g[k][0]); } } int time = 0; void dfs_hld(int k){ in[k] = time++; for(auto e:g[k]){ if(e.to == par[k])continue; head[e.to] = (e.to == g[k][0].to ? head[k]: e.to); edges[time] = e; dfs_hld(e.to); } out[k] = time; } int lca(int p,int q){ while(1){ if(in[p] < in[q])swap(p,q); if(head[p] == head[q])return q; p = par[head[p]]; } } vector>query_path(int p,int q,bool isEdge){ int r=lca(p,q); vector>ret; for(int i=0;i<2;i++){ if(i == 1)swap(p,q); while(1){ if(isEdge&&p==r)break; if(head[p]==head[r]){ ret.emplace_back(in[r]+(isEdge?1:i),in[p]+1); break; } ret.emplace_back(in[head[p]],in[p]+1); p = par[head[p]]; } } return ret; } vector>>query_order_path(int p,int q,bool isEdge){ //非可換クエリ用、配列0を順番を反転したデータ構造に、配列1を通常のデータ構造に vector>>ret(2); int r=lca(p,q); for(int i=0;i<2;i++){ if(i == 1)swap(p,q); while(1){ if(isEdge&&p==r)break; if(head[p]==head[r]){ if(i==0) ret[i].emplace_back(n-(in[p]+1),n-(in[r]+(isEdge?1:i))); else ret[i].emplace_back(in[r]+(isEdge?1:i),in[p]+1); break; } if(i==0) ret[i].emplace_back(n-(in[p]+1),n-(in[head[p]])); else ret[i].emplace_back(in[head[p]],in[p]+1); p = par[head[p]]; } } reverse(ret[1].begin(), ret[1].end()); return ret; } pairquery_subtree(int p,bool isEdge){ return make_pair(in[p]+isEdge,out[p]); } //uのv方向の子 子孫関係は前もって確認すること(in,outを見る) int child(int u,int v){ while(1){ if(head[u]==head[v]){ v=g[u][0].to; break; } v=head[v]; if(par[v]==u)break; v=par[v]; } return v; } //uをv方向に一つ進めた頂点 int move(int u,int v){ assert(u!=v); if(in[u]rev_in; int climb(int u,int k){ if(rev_in.empty()){ rev_in.resize(n); for(int i=0;i(dep[u]-k, 0); while(dep[u]>nd){ if(dep[head[u]]>nd){ u=par[head[u]]; } else{ u=rev_in[in[head[u]]+nd-dep[head[u]]]; } } return u; } int jump(int from,int to, int k){ int r = lca(from, to); int d1 = dep[from] - dep[r]; int d2 = dep[to] - dep[r]; if(d1 + d2 < k)return -1; else if(k <= d1)return climb(from, k); else return climb(to, d1 + d2 - k); } template Graphlca_tree(vector&v){ auto compare=[&](int x,int y){return in[x]ret(sz2); stackst; for(int i=0;i struct StaticToptree{ const HLD &hld; int count; int root; vectorl,r,p; vectoraff; T edge_identity; StaticToptree(const HLD &hld):hld(hld),edge_identity(edge_identity),count(hld.n),l(hld.n*2,-1),r(hld.n*2,-1),p(hld.n*2,-1),aff(hld.n*2,VERTEX){ root = dfs(hld.in[0],-1).second; } //sz,vid pairdfs(int v,int par){ int sub=0; vectorvs; vectorsz; int now=v,pre=par; while(1){ int sum_sz=1; //vid,eid priority_queue,vector>,greater>>pq; for(int i=1;i=2){ auto [sx,x]=pq.top();pq.pop(); auto [sy,y]=pq.top();pq.pop(); int nv=count++; aff[nv]=LIGHT; l[nv]=x; p[x]=nv; r[nv]=y; p[y]=nv; pq.emplace(sx+sy,nv); } int last=now; if(!pq.empty()){ auto [sx,x]=pq.top();pq.pop(); int nv=count++; aff[nv]=HEAVY_LIGHT; l[nv]=now; p[x]=nv; r[nv]=x; p[now]=nv; last=nv; } vs.push_back(last); sz.push_back(sum_sz); if(hld.g[now].empty()||hld.g[now][0]==pre)break; pre=now; now=hld.g[now][0]; } vectorcsz(sz.size()+1); for(int i=0;iint{ {} if(ls+1==rs){ return vs[ls]; } int sum=csz[rs]-csz[ls]; int lv=-1,rv=-1; if(sz[ls]*2>=sum){ lv=rec(rec,ls,ls+1); rv=rec(rec,ls+1,rs); } else if(sz[rs-1]*2>=sum){ lv=rec(rec,ls,rs-1); rv=rec(rec,rs-1,rs); } else{ int ri=min(rs-1,lower_bound(csz.begin(),csz.end(),csz[ls]+(sum+1)/2)-csz.begin()); int li=max(ls+1,ri-1); if(abs((csz[li]-csz[ls])*2-sum) struct DynamicReRooting{ const StaticToptree &t; vectorseg,ges; const F1 &fh; const F2 &fl; const F3 &fhl; const V &M1; vectorpath; DynamicReRooting(const StaticToptree &t,const F1 &heavy_merge,const F2 &light_merge,const F3 &heavy_light_merge,const V &M1): t(t),fh(heavy_merge),fl(light_merge),fhl(heavy_light_merge),M1(M1){ seg.assign(t.aff.size(),M1); ges.assign(t.aff.size(),M1); } void set(int k,V val){ seg[k]=val; ges[k]=val; } void recalc(int k){ if(t.aff[k]==LIGHT){ seg[k]=fl(seg[t.l[k]],seg[t.r[k]]); } else if(t.aff[k]==HEAVY){ seg[k]=fh(seg[t.l[k]],seg[t.r[k]]); ges[k]=fh(ges[t.r[k]],ges[t.l[k]]); } else if(t.aff[k]==HEAVY_LIGHT){ seg[k]=fhl(seg[t.l[k]],seg[t.r[k]]); ges[k]=seg[k]; } } void build(){ for(int i=0;i=path.size())path.push_back(0); path[cnt++]=k; if(t.p[k]==-1)break; k=t.p[k]; } return cnt; } //head,tail,light tupleget(int k){ int m=root_path(k); V head=M1,tail=M1,light=M1; int hl=-1; for(int i=m-1;i>=1;i--){ if(t.aff[path[i]]==HEAVY){ if(t.l[path[i]]==path[i-1]){ tail=fh(seg[t.r[path[i]]],tail); } else{ auto lt=ges[t.l[path[i]]]; //OUT("kotti?",path[i-1],lt.arg,lt.tail,head.arg,head.tail,head.head); head=fh(ges[t.l[path[i]]],head); } } else if(t.aff[path[i]]==HEAVY_LIGHT){ if(i==1&&k==t.l[path[i]])light=seg[t.r[path[i]]]; else hl=t.l[path[i]]; } else{ //LIGHT if(t.l[path[i]]==path[i-1]){ light=fh(seg[t.r[path[i]]],light); } else{ light=fh(seg[t.l[path[i]]],light); } } if(hl!=-1&&t.aff[path[i-1]]!=LIGHT){ head=fhl(seg[hl],fl(light,fl(head,tail))); tail=M1; light=M1; hl=-1; } //OUT(t.aff); //OUT(head.arg,tail.arg,light.arg,hl,t.l[path[i]],t.r[path[i]]); } return make_tuple(head,tail,light); } V reroot(int k){ auto [head,tail,light]=get(k); return fhl(seg[k],fl(light,fl(head,tail))); } }; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll res=0,buf=0; bool judge = true; int n;cin>>n; auto g=readGraph(n,n-1); struct A{ int head,tail,arg; }; A init{-1,-1,-1}; auto fh=[](A h,A t)->A{ {} if(t.arg==-1)return h; if(h.arg==-1)return t; //OUT(t.arg,t.head,h.tail,h.arg); if(t.headA{ {} if(t.arg==-1)return h; return {h.head,t.head,t.arg}; }; auto fl=[](A h,A t)->A{ {} if(h.arg==-1)return t; if(t.arg==-1)return h; if(t.head>h.head)return t; return h; }; HLD hld(g,2); StaticToptree tr(hld); DynamicReRooting seg(tr,fh,fl,fhl,init); //OUT(tr.p,seg.t.r); rep(i,0,n){ seg.set(i,A{i,-1,i}); } seg.build(); vectorp(n); iota(ALL(p),0); int x=0; int q;cin>>q; while(q--){ int u,v;cin>>u>>v; u=(u+n-1+x)%n; v=(v+n-1+x)%n; swap(p[u],p[v]); seg.update(u,A{p[u],-1,u}); seg.update(v,A{p[v],-1,v}); //OUT(p); //OUT(u,v); /*rep(i,0,2*n){ OUT(i); OUT(seg.seg[i].arg); OUT(seg.ges[i].arg); }*/ auto ret=seg.reroot(u); x=ret.arg+1; cout<