splay维护dfs序
暴力传标记，不过一定要把标记传利索(并不是oi用语)了
还以为会有什麽高端操作。。。
上代码：
#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; int n,m,cnt,tot,rt,tp=1,to; char ac[3]; int fa[100005]; int head[100005]; ll w[100005]; int st[200005]; int sk[200005]; int id[200005]; struct node{ int in; int out; }poi[200005]; struct Edge{ int fr; int to; int nxt; }edge[100005]; struct Tree{ ll sum; ll val; ll tag; int fa; int in_num; int out_num; int son[2]; }tr[200005]; void init(){ memset(head,-1,sizeof(head)); } void addedge(int f,int t){ cnt++; edge[cnt].fr=f; edge[cnt].to=t; edge[cnt].nxt=head[f]; head[f]=cnt; } void pushup(int x){ tr[x].sum=tr[tr[x].son[0]].sum+tr[tr[x].son[1]].sum+tr[x].val; tr[x].in_num=tr[tr[x].son[0]].in_num+tr[tr[x].son[1]].in_num+(id[x]==1); tr[x].out_num=tr[tr[x].son[0]].out_num+tr[tr[x].son[1]].out_num+(id[x]==-1); } void update(int x,int z){ if(!x)return; tr[x].sum+=(ll)(tr[x].in_num-tr[x].out_num)*z; tr[x].val+=(ll)id[x]*z; tr[x].tag+=z; } void markdown(int x){ if(!x)return; if(tr[x].tag){ update(tr[x].son[0],tr[x].tag); update(tr[x].son[1],tr[x].tag); tr[x].tag=0; } } void rotate(int x){ int y=tr[x].fa,z=tr[y].fa; int typ=(x==tr[y].son[1]); tr[y].son[typ]=tr[x].son[typ^1],tr[tr[x].son[typ^1]].fa=y; tr[x].son[typ^1]=y,tr[y].fa=x; tr[x].fa=z; if(z){ if(y==tr[z].son[0])tr[z].son[0]=x; else tr[z].son[1]=x; } pushup(y);pushup(x); } void splay(int x,int goal){ sk[to=1]=x; for(int u=x;u!=rt;u=tr[u].fa){ sk[++to]=tr[u].fa; } while(to){ markdown(sk[to--]); } for(int y;(y=tr[x].fa)!=goal;rotate(x)){ if(tr[y].fa!=goal){ rotate((x==tr[y].son[0])==(y==tr[tr[y].fa].son[0])?y:x); } } if(!goal)rt=x; } void insert(int x,ll v){ int u; while(true){ u=tr[x].son[1]; if(!u){ u=++tot; tr[u].val=v;tr[u].fa=x; tr[x].son[1]=u; pushup(u); break; } x=u; } splay(u,0); } int findpre(int x){ int u=tr[x].son[0]; while(tr[u].son[1])u=tr[u].son[1]; return u; } int findsuc(int x){ int u=tr[x].son[1]; while(tr[u].son[0])u=tr[u].son[0]; return u; } int findla(int x){ while(tr[x].son[1])x=tr[x].son[1]; return x; } void work(int x,int y){ splay(poi[x].in,0); int a=findpre(poi[x].in); splay(poi[x].out,0); int b=findsuc(poi[x].out); splay(a,0); splay(b,a); int s=tr[b].son[0]; tr[b].son[0]=0;pushup(b); splay(poi[y].in,0); int c=findsuc(rt); splay(c,rt); tr[c].son[0]=s;tr[s].fa=c; pushup(c); } void gettag(int x,ll v){ splay(poi[x].in,0); int a=findpre(poi[x].in); splay(poi[x].out,0); int b=findsuc(poi[x].out); splay(a,0); splay(b,a); int s=tr[b].son[0]; tr[s].val+=id[s]*v; tr[s].tag+=v; } ll query(int x){ splay(poi[x].in,0); int a=findsuc(poi[x].in); splay(1,0); splay(a,1); return tr[tr[a].son[0]].sum; } void dfs(int u){ st[++tp]=u; poi[u].in=tp;id[tp]=1; insert(rt,w[u]); for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; dfs(v); } st[++tp]=u; poi[u].out=tp;id[tp]=-1; insert(rt,-w[u]); } int main(){ init(); insert(rt,0); scanf("%d",&n); for(int i=2;i<=n;i++){ scanf("%d",&fa[i]); addedge(fa[i],i); } for(int i=1;i<=n;i++){ scanf("%lld",&w[i]); } dfs(1); insert(rt,0); scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%s",ac+1); if(ac[1]=='Q'){ int d; scanf("%d",&d); printf("%lld ",query(d)); } else if(ac[1]=='C'){ int x,y; scanf("%d%d",&x,&y); work(x,y); } else{ int p;ll q; scanf("%d%lld",&p,&q); gettag(p,q); } } return 0; }