洛谷 P4074 [WC2013]糖果公园 解题报告

P4074 [WC2013]糖果公园

糖果公园

---

树上待修莫队

注意一个思想，dfn序处理链的方法，必须可以根据类似异或的东西，然后根据lca分两种情况讨论

注意细节

---

Code:

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cctype>

#define ll long long

const int N=2e5+10;

inline int read()

{

    int x=0;char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) x=x*10+c-'0',c=getchar();

    return x;

}

struct modi

{

    int x,y,pre;

    modi(){}

    modi(int x,int y,int pre){this->x=x,this->y=y,this->pre=pre;}

}dew[N];

int n,m,q,Q,Mi,l,r,Ti,V[N],W[N],C[N],las[N],B;

struct qry

{

    int l,r,lp,rp,ti,ad,id;

    qry(){}

    qry(int L,int R,int Ti,int Ad,int Id)

    {

        l=L,r=R,ti=Ti,ad=Ad,id=Id;

        lp=(L-1)/B+1,rp=(R-1)/B+1;

    }

    bool friend operator <(qry a,qry b)

    {

        return a.lp==b.lp?(a.rp==b.rp?a.ti<b.ti:a.rp<b.rp):a.lp<b.lp;

    }

}bee[N];

int head[N],to[N],Next[N],cnt;

void add(int u,int v)

{

    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

int f[N][20],dep[N],dfn[N],low[N],ha[N],dfsclock;

void dfs(int now)

{

    ha[dfn[now]=++dfsclock]=now;

    dep[now]=dep[f[now][0]]+1;

    for(int i=1;f[now][i-1];i++) f[now][i]=f[f[now][i-1]][i-1];

    for(int v,i=head[now];i;i=Next[i])

        if((v=to[i])!=f[now][0])

            f[v][0]=now,dfs(v);

    ha[low[now]=++dfsclock]=now;

}

int LCA(int x,int y)

{

    if(dep[x]<dep[y]) return LCA(y,x);

    for(int i=18;~i;i--)

        if(dep[f[x][i]]>=dep[y])

            x=f[x][i];

    if(x==y) return x;

    for(int i=18;~i;i--)

        if(f[x][i]!=f[y][i])

            x=f[x][i],y=f[y][i];

    return f[x][0];

}

int tag[N],ct[N];

ll Ans[N],ans;

void ins(int p){ans+=1ll*W[++ct[C[p]]]*V[C[p]];}

void del(int p){ans-=1ll*W[ct[C[p]]--]*V[C[p]];}

void upd(int p)

{

    if(tag[p]) del(p);

    else ins(p);

    tag[p]^=1;

}

void rig(int T)

{

    int p=dew[T].x;

    if(!tag[p]) {C[p]=dew[T].y;return;}

    del(p);

    C[p]=dew[T].y;

    ins(p);

}

void lef(int T)

{

    int p=dew[T].x;

    if(!tag[p]) {C[p]=dew[T].pre;return;}

    del(p);

    C[p]=dew[T].pre;

    ins(p);

}

int main()

{

    n=read(),m=read(),q=read();

    for(int i=1;i<=m;i++) V[i]=read();//第i种权值V_i

    for(int i=1;i<=n;i++) W[i]=read();//第i次吃某种权值为W_i

    for(int u,v,i=1;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);

    dfs(1);

    for(int i=1;i<=n;i++) las[i]=C[i]=read();//种类为C_i

    B=pow(1.0*dfsclock,2.0/3.0)+1;

    for(int ty,x,y,i=1;i<=q;i++)

    {

        ty=read(),x=read(),y=read();

        if(ty)//qry

        {

            if(dfn[x]>dfn[y]) std::swap(x,y);

            int lca=LCA(x,y);++Q;

            if(x==lca) bee[Q]=qry(dfn[x],dfn[y],Mi,0,Q);

            else bee[Q]=qry(low[x],dfn[y],Mi,lca,Q);

        }

        else

            dew[++Mi]=modi(x,y,las[x]),las[x]=y;

    }

    std::sort(bee+1,bee+1+Q);

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

    {

        while(l<bee[i].l) upd(ha[l++]);

        while(l>bee[i].l) upd(ha[--l]);

        while(r<bee[i].r) upd(ha[++r]);

        while(r>bee[i].r) upd(ha[r--]);

        while(Ti<bee[i].ti) rig(++Ti);

        while(Ti>bee[i].ti) lef(Ti--);

        if(bee[i].ad) ins(bee[i].ad);

        Ans[bee[i].id]=ans;

        if(bee[i].ad) del(bee[i].ad);

    }

    for(int i=1;i<=Q;i++) printf("%lld\n",Ans[i]);

    return 0;

}

---

2019.1.30