题目链接：http://www.lydsy.com:808/JudgeOnline/problem.php?id=3460

题意：一棵树。每个节点住一个人，这个人打水的时间为Ti。每次查询一个路径。这个路径上的人都去一个水管前打水。总的最小等待时间。

思路：在树的DFS序中分块。

const int N=200005;struct node{	int x,y,lca,flag,id;	int t;};vector
     
       b;vector
      
        g[N];vector
       
        
          > Q[N];int n,m,key,d[N];int S[N],id;int mp[N],pos[N][2];int get(int x){	if(S[x]!=x) S[x]=get(S[x]);	return S[x];}int visit[N];void dfs(int u,int pre){	pos[u][0]=++id;	mp[id]=u;	int i;	for(i=0;i
         
          b.y; 	return a.y
          
           rr) add(R--); while(L
           
            ll) add(--L); if(b[i].flag) add(pos[b[i].lca][0]); ans[id][t]=Ans; if(b[i].flag) add(pos[b[i].lca][0]); }}int main(){ n=getInt(); m=getInt(); key=getInt(); int i; for(i=1;i<=n;i++) d[i]=getInt(),dp[i]=d[i]; sort(dp+1,dp+n+1); M=unique(dp+1,dp+n+1)-(dp+1); for(i=1;i<=n;i++) d[i]=lower_bound(dp+1,dp+M+1,d[i])-dp; int root; for(i=1;i<=n;i++) { int x=getInt(); if(!x) root=i; else g[x].pb(i),g[i].pb(x); } int cnt=0; for(i=1;i<=m;i++) { char op[5]; scanf("%s",op); if(op[0]=='C') root=getInt(); else { int x=getInt(); node a; a.x=x%n+1; a.y=root; a.id=i; a.t=0; b.pb(a); Q[a.x].pb(MP(a.y,cnt)),Q[a.y].pb(MP(a.x,cnt)); cnt++; a.x=(x+key)%n+1; a.y=root; a.id=i; a.t=1; b.pb(a); Q[a.x].pb(MP(a.y,cnt)),Q[a.y].pb(MP(a.x,cnt)); cnt++; } } for(i=1;i<=n;i++) S[i]=i; dfs(1,0); for(i=0;i
            
             pos[b[i].y][0]) swap(b[i].x,b[i].y); b[i].x=pos[b[i].x][1]; b[i].y=pos[b[i].y][0]; b[i].flag=1; } clr(ans,-1); deal(); int last=0; for(i=1;i<=m;i++) if(ans[i][0]!=-1||ans[i][1]!=-1) { printf("%lld\n",ans[i][last&1]); last=ans[i][last&1]; }}