BZOJ3052: [wc2013]糖果公园

Description

Input

Output

Sample Input

Sample Input

 

Sample Output

84
131
27
84

HINT

基本是照着何神的代码写的。

传说中的树上带修莫队。

按N^(2/3)对树分块，然后三维莫队。

#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=1<<16;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
    if(head==tail) {
        int l=fread(buffer,1,BufferSize,stdin);
        tail=(head=buffer)+l;
    }
    return *head++;
}
inline int read() {
    int x=0,f=1;char c=Getchar();
    for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
    for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
    return x*f;
}
typedef long long ll;
const int maxn=100010;
const int SIZE=2000;
ll v[maxn],w[maxn],curans,ans[maxn];
int n,m,q,c[maxn],blo[maxn],first[maxn],next[maxn<<1],to[maxn<<1],e;
void AddEdge(int u,int v) {
    to[++e]=v;next[e]=first[u];first[u]=e;
    to[++e]=u;next[e]=first[v];first[v]=e;
}
int S[maxn],C[maxn],anc[maxn][20],dep[maxn],top,ToT;
void dfs(int x) {
    dep[x]=dep[anc[x][0]]+1;C[x]=top;
    rep(i,1,19) anc[x][i]=anc[anc[x][i-1]][i-1];
    ren if(to[i]!=anc[x][0]) {
        anc[to[i]][0]=x;dfs(to[i]);
        if(top-C[x]>SIZE) {
            ToT++;while(top>C[x]) blo[S[top--]]=ToT;
        }
    }
    S[++top]=x;
}
int lca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    dwn(i,19,0) if(1<<i<=dep[x]-dep[y]) x=anc[x][i];
    dwn(i,19,0) if(anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
    return x==y?x:anc[x][0];
}
struct Query {
    int x,y,t,id;
    bool operator < (const Query& ths) const {
        if(blo[x]!=blo[ths.x]) return blo[x]<blo[ths.x];
        if(blo[y]!=blo[ths.y]) return blo[y]<blo[ths.y];
        return t<ths.t;
    }
}Q[maxn];
int X[maxn],Y[maxn],Z[maxn],vis[maxn],tot[maxn],cnt;
void U(int x) {
    int k=c[x];
    if(!vis[x]) tot[k]++,curans+=w[tot[k]]*v[k];
    else curans-=w[tot[k]]*v[k],tot[k]--;
    vis[x]^=1;
}
void change(int x,int k) {
    if(vis[x]) U(x),c[x]=k,U(x);
    else c[x]=k;
}
void update(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) U(x),x=anc[x][0];
    while(x!=y) U(x),U(y),x=anc[x][0],y=anc[y][0];
}
int main() {
    n=read();m=read();q=read();
    rep(i,1,m) v[i]=read();
    rep(i,1,n) w[i]=read();
    rep(i,2,n) AddEdge(read(),read());
    rep(i,1,n) c[i]=read();
    dfs(1);m=0;
    while(top) blo[S[top--]]=ToT;
    rep(i,1,q) {
        int t=read(),x=read(),y=read();
        if(t==0) X[++cnt]=x,Y[cnt]=c[x],c[x]=Z[cnt]=y;
        else {
            if(blo[x]>blo[y]) swap(x,y);
            Q[++m]=(Query){x,y,cnt,i};
        }
    }
    sort(Q+1,Q+m+1);
    int cu=1,cv=1,t=cnt;
    rep(i,1,m) {
        int x=Q[i].x,y=Q[i].y,z=lca(x,y);
        while(t<Q[i].t) t++,change(X[t],Z[t]);
        while(t>Q[i].t) change(X[t],Y[t]),t--;
        update(x,cu);update(y,cv);
        U(z);ans[Q[i].id]=curans;U(z);
        cu=x;cv=y;
    }
    rep(i,1,q) if(ans[i]) printf("%lld
",ans[i]);
    return 0;
}