BZOJ3052: [wc2013]糖果公园

树上的带修莫队模板

分块用刚才的王室联邦分快法

然后套带修莫队模板

//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<ctime>
#include<cmath>
typedef long long LL;
using namespace std;
const int N=100000+7;
int n,m,q,cq,cx,mxsz,is[N],now,px,py;
LL sum,ans[N],v[N],w[N],c[N];

template<typename T> void read(T &x) {
    char ch=getchar(); x=0; T f=1;
    while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if(ch=='-') f=-1,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; x*=f;
}

struct node{
    int ti,x,y,pp;
    node(){}
    node(int ti,int x,int y,int pp):ti(ti),x(x),y(y),pp(pp){}
}qs[N],cg[N]; 

int ecnt,fir[N],nxt[N*2],to[N*2],f[N][20];
void add(int u,int v) {
    nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v;
    nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u;
}

int sta[N],top,id[N],R[N],dfn[N],dfs_clock,tot;
void dfs(int x,int fa) {
    int bot=top;
    dfn[x]=++dfs_clock;
    f[x][0]=fa; 
    R[x]=R[fa]+1;
    for(int i=fir[x];i;i=nxt[i]) if(to[i]!=fa) {
        dfs(to[i],x);
        if(top-bot>=mxsz) {
            ++tot;
            while(top>bot) 
                id[sta[top--]]=tot;
        }
    }
    sta[++top]=x;
} 

bool cmp(const node&A,const node&B) {
    return id[A.x]==id[B.x]?(id[A.y]==id[B.y]?(A.pp<B.pp):id[A.y]<id[B.y]):id[A.x]<id[B.x];
}

void pre() {
    for(int i=1;i<20;i++)
        for(int j=1;j<=n;j++)
            f[j][i]=f[f[j][i-1]][i-1];
}

int lca(int x,int y) {
    if(R[x]<R[y]) swap(x,y);
    for(int i=19;i>=0;i--)
        if(R[f[x][i]]>=R[y])
            x=f[x][i];
    if(x==y) return x;
    for(int i=19;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}

int cnt[N],vis[N];
void change(int x,int f) {
    if(f) {
        cnt[c[x]]++;
        sum+=(LL)w[cnt[c[x]]]*v[c[x]];
    }
    else {
        sum-=(LL)w[cnt[c[x]]]*v[c[x]];
        cnt[c[x]]--;
    }
}

void fz(int x,int y) {
    int z=lca(x,y);
    for(int i=x;i!=z;i=f[i][0]) 
        change(i,vis[i]^=1);
    for(int i=y;i!=z;i=f[i][0]) 
        change(i,vis[i]^=1);
} 

int pr[N],ls[N];
void work() {
    sort(qs+1,qs+cq+1,cmp);
    for(int i=1;i<=cx;i++) {
        if(!ls[cg[i].x]) ls[cg[i].x]=c[cg[i].x];
        pr[i]=ls[cg[i].x]; ls[cg[i].x]=cg[i].y;
    }
    int now=0;
    for(int i=1;i<=cq;i++) {
        int x=qs[i].x,y=qs[i].y;
        int z=lca(x,y);
        for(int j=qs[i-1].pp+1;j<=qs[i].pp;j++) {
            if(vis[cg[j].x]) change(cg[j].x,0); 
            c[cg[j].x]=cg[j].y;
            if(vis[cg[j].x]) change(cg[j].x,1); 
        }
        for(int j=qs[i-1].pp;j>qs[i].pp;j--) {
            if(vis[cg[j].x]) change(cg[j].x,0); 
            c[cg[j].x]=pr[j];
            if(vis[cg[j].x]) change(cg[j].x,1); 
        }
        if(i==1) fz(x,y); 
        else {fz(qs[i-1].x,x); fz(qs[i-1].y,y);}
        change(z,vis[z]^=1);
        ans[qs[i].ti]=sum;
        change(z,vis[z]^=1);
    }
    for(int i=1;i<=q;i++) 
        if(is[i]) printf("%lld
",ans[i]);
}

void init() {
    read(n); read(m); read(q);
    mxsz=pow(n,2.0/3)*0.5;
    for(int i=1;i<=m;i++) read(v[i]);
    for(int i=1;i<=n;i++) read(w[i]);
    for(int i=1;i<n;i++) {
        int u,v;
        read(u); read(v);
        add(u,v);
    }
    dfs(1,0); 
    pre();
    while(top) id[sta[top--]]=tot;
    for(int i=1;i<=n;i++) read(c[i]);
    for(int i=1;i<=q;i++) {
        int o,x,y;
        read(o); read(x); read(y);
        if(o&&dfn[x]>dfn[y]) swap(x,y);
        if(o) qs[++cq]=node(i,x,y,cx),is[i]=1;
        else cg[++cx]=node(i,x,y,0);
    }
}

int main() {
    init();
    work();
    return 0;
}