P4074 [WC2013]糖果公园

思路

带修莫队+树上莫队
注意代码细节即可，答案的维护非常简单

蒟蒻的大常数代码

#include 
#include 
#include 
#include 
#include 
using namespace std;
int vx[100100*2],fir[100100],nxt[100100*2],cnt;
void addedge(int ui,int vi){
    ++cnt;
    vx[cnt]=vi;
    nxt[cnt]=fir[ui];
    fir[ui]=cnt;
}
int color[100100],w_p[100100],b_p[100100],b[100100],tx,n,m,q,v[100100],w[100100],U,V,T,in_ans[100100],belong[100100],times[100100];
long long sum,ans[100100];
struct Query{
    int t,u,v,id;
    bool operator < (const Query &b) const{
        return (belong[u]==belong[b.u])?((belong[v]==belong[b.v])?t S;
void T_modi(int t,int opt){
    if(opt==1){
        if(in_ans[A[t].x]){
            sum-=1LL*v[A[t].before]*w[color[A[t].before]];
            color[A[t].before]--;
            color[A[t].after]++;
            sum+=1LL*v[A[t].after]*w[color[A[t].after]];
        }
        w_p[A[t].x]=A[t].after;
    }
    else{
        if(in_ans[A[t].x]){
            sum-=1LL*v[A[t].after]*w[color[A[t].after]];
            color[A[t].after]--;
            color[A[t].before]++;
            sum+=1LL*v[A[t].before]*w[color[A[t].before]];
        }
        w_p[A[t].x]=A[t].before;
    }
    T+=opt;
}
void modi_point(int x){
    if(in_ans[x]){
        sum-=1LL*v[w_p[x]]*w[color[w_p[x]]];
        color[w_p[x]]--;
    }
    else{
        color[w_p[x]]++;
        sum+=1LL*v[w_p[x]]*w[color[w_p[x]]];
    }
    in_ans[x]^=1;
}
void modi_path(int x,int y){
    if(dep[x]dep[y]){
        modi_point(x);
        x=jump[x][0];
    }
    while(x!=y){
        modi_point(x);
        modi_point(y);
        x=jump[x][0];
        y=jump[y][0];
    }
}
void dfs(int u,int f){
    jump[u][0]=f;
    for(int i=1;i<20;i++)
        jump[u][i]=jump[jump[u][i-1]][i-1];
    dep[u]=dep[f]+1;
    int t=S.size();
    for(int i=fir[u];i;i=nxt[i]){
        if(vx[i]==f)
            continue;
        dfs(vx[i],u);
        if(S.size()-t>=sz){
            block_cnt++;
            while(S.size()>t){
                belong[S.top()]=block_cnt;
                S.pop();
            }
        }
    }
    S.push(u);
}
void init(void){
    sz=pow(n,0.6666666);
    dfs(1,0);
    while(!S.empty()){
        belong[S.top()]=block_cnt;
        S.pop();
    }
}
int lca(int x,int y){
    if(dep[x]=0;i--)
        if(dep[jump[x][i]]>=dep[y])
            x=jump[x][i];
    if(x==y)
        return x;
    for(int i=19;i>=0;i--)
        if(jump[x][i]!=jump[y][i])
            x=jump[x][i],y=jump[y][i];
    return jump[x][0];
}
int main(){
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<=m;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;iQ[i].t)
            T_modi(T,-1);
        int Lca=lca(U,V);
        modi_point(Lca);
        ans[Q[i].id]=sum;
        modi_point(Lca);
    }
    for(int i=1;i<=Qcnt;i++)
        printf("%lld\n",ans[i]);
    return 0;
}