【GDOI2016模拟3.15】染色

SOL：

  把路径拆成dep[x]+dep[y]-2*dep[lca(x,y)].

  问题变成求dep[lca(x,y)]，树剖即可。

  

#include<bits/stdc++.h>
#define N 500007
#define Mid (l+r>>1)
#define ls no<<1,l,Mid
#define rs no<<1|1,Mid+1,r
#define LL long long
#define eho(x) for(int i=head[x];i;i=net[i])
#define v fall[i]
using namespace std;
int fall[N],net[N],head[N],tot,col[N];
inline void add(int x,int y){
    fall[++tot]=y; net[tot]=head[x]; head[x]=tot;
}
int siz[N],son[N],p[N],lazy[N],f[N],top[N],a[N],to,in[N],n,m,op,x,now[N];
LL dep[N],t[N],xo,kkk,sum[N];
void dfs1(int x,int fa){
    siz[x]=1; dep[x]=dep[fa]+a[x];
    eho(x) if (v^fa) {
        dfs1(v,x);
        siz[x]+=siz[v];
        if (siz[son[x]]<siz[v]) son[x]=v;
    }
//    eho(x) if (v^fa) assert(siz[son[x]]>=siz[v]);
}
void dfs2(int x,int tops) {
    p[++to]=x; in[x]=to; top[x]=tops;  
    if (son[x]) dfs2(son[x],tops);
    eho(x) if ((v^f[x])&&(v^son[x])) dfs2(v,v);
}
void build(int no,int l,int r) {
    if (l==r) {t[no]=a[p[l]]; return;} 
    build(ls); build(rs);
    t[no]=t[no<<1]+t[no<<1|1];
//    if (t[no]!=sum[r]-sum[l-1]) {
//        cout<<no<<' '<<l <<' '<<r<<endl;
//        assert(0);
//    }
}
void down(int no) {
    if (!lazy[no]) return;
    lazy[no<<1]+=lazy[no],lazy[no<<1|1]+=lazy[no],
    now[no<<1]+=lazy[no]*t[no<<1],now[no<<1|1]+=lazy[no]*now[no<<1|1],
    lazy[no]=0;
}
void add(int no,int l,int r,int L,int R){
    if (L<=l&&r<=R) {lazy[no]++;now[no]+=t[no]; return;}
    down(no);
    if (L<=Mid) add(ls,L,R);
    if (R> Mid) add(rs,L,R);
    now[no]=now[no<<1]+now[no<<1|1];
}    
LL ans=0,pp;
void query(int no,int l,int r,int L,int R){
    if (L<=l&&r<=R) {ans+=now[no]; return;}
    if (l==1&&r==2) {
        pp==0;
    }
    down(no);
    if (L<=Mid) query(ls,L,R);
    if (R> Mid) query(rs,L,R);
    if (now[no<<1]+now[no<<1|1]!=now[no]) {
        cout<<no<<' '<<l<<' '<<r<<endl;
        cout<<now[no]<<' '<<now[no<<1]<<' '<<now[no<<1|1]<<endl;
        cout<<lazy[no]<<' '<<lazy[no<<1]<<' '<<lazy[no<<1|1]<<endl;
    }
    assert(now[no<<1]+now[no<<1|1]==now[no]);
//    now[no]=now[no<<1]+now[no<<1|1];
}
void change(int x){
    while (x) {
        add(1,1,n,in[top[x]],in[x]);
        x=f[top[x]];
    }
} 
LL query(int x) {
    ans=0;
    while (x) {
        query(1,1,n,in[top[x]],in[x]);
        x=f[top[x]]; 
    } return ans;
}
signed main () {
    freopen("color1.in","r",stdin);
//    freopen("11.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=2;i<=n;i++) scanf("%d",f+i),f[i]++;
    for (int i=2;i<=n;i++) {
        scanf("%d",a+i); add(f[i],i);
    }
    
    dfs1(1,0); dfs2(1,1);
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[p[i]];
    build(1,1,n);
//    for (int i=1;i<=n;i++) printf("%d ",dep[i]);
    while (m--) {
        scanf("%d%d",&op,&x),x++;
        if (op==1&&!col[x]) change(x),xo+=dep[x],kkk++,col[x]++; 
        else if (op==2) printf("%lld
",xo+kkk*dep[x]-2*query(x));
    } return 0;
}