P4074 [WC2013]糖果公园

思路

带修莫队+树上莫队

注意代码细节即可，答案的维护非常简单
蒟蒻的大常数代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cmath>

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<b.t:belong[v]<belong[b.v]):belong[u]<belong[b.u];

    }

}Q[100100];

struct Modi{

    int x,before,after;

}A[100100];

int jump[100100][20],dep[100100],sz,block_cnt,Acnt,Qcnt;

stack<int> 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])

        swap(x,y);

    while(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]<dep[y])

        swap(x,y);

    for(int i=19;i>=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;i<n;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        addedge(a,b);

        addedge(b,a);

    }

    for(int i=1;i<=n;i++)

        scanf("%d",&w_p[i]),b_p[i]=b[i]=w_p[i];

    for(int i=1;i<=q;i++){

        int opt,x,y;

        scanf("%d %d %d",&opt,&x,&y);

        if(opt==0){

            A[++Acnt].x=x;

            A[Acnt].before=b_p[x];

            A[Acnt].after=y;

            b_p[x]=y;

        }

        else{

            Q[++Qcnt].t=Acnt;

            Q[Qcnt].u=x;

            Q[Qcnt].v=y;

            Q[Qcnt].id=Qcnt;

        }

    }

    init();

    sort(Q+1,Q+Qcnt+1);

    U=V=1;

    T=0;

    for(int i=1;i<=Qcnt;i++){

        modi_path(U,Q[i].u);

        modi_path(V,Q[i].v);

        U=Q[i].u;

        V=Q[i].v;

        while(T<Q[i].t)

            T_modi(T+1,1);

        while(T>Q[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;

}
巴特西

P4074 [WC2013]糖果公园

思路

蒟蒻的大常数代码

最新文章

热门文章
