不懂为啥会爆零输出(除开#1 3 4全部wa),希望巨佬可以不吝赐教

P4074 [WC2013] 糖果公园

lzlwddl @ 2022-08-15 15:22:47

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+7;
int read() {
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
int n,m,qq,siz,top,cnt1,cnt2,ti=0,curl=1,curr=0;
int v[maxn],w[maxn],fa[maxn],c[maxn],sta[maxn],st[maxn],ed[maxn],isp[maxn];
vector <int> g[maxn],son[maxn],bh[maxn];
struct que
{
    int l,r,id,lca,p;
} q[maxn];
void dfs(int x,int f)
{
    sta[++top]=x;st[x]=top; 
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if(y==f)continue;
        dfs(y,x); 
    }
    sta[++top]=x;ed[x]=top; 
}
struct node
{
    int x,k,kk;
} h[maxn];
bool cmp(que i,que j)
{
    if(i.l/siz==j.l/siz)
    {
        if(i.r/siz==j.r/siz)return i.p>j.p;
        return i.r<j.r;
    }
    return i.l/siz<j.l/siz;
}
int get(int p){ return p==fa[p]?fa[p]:fa[p]=get(fa[p]);}
void tarjan(int x)
{
    isp[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if(isp[y])continue;
        tarjan(y);
        fa[y]=x;
    }
    for(int i=0;i<son[x].size();i++)
    {
        int y=son[x][i],cnt=bh[x][i];
        if(isp[y]==2)q[cnt].lca=get(y);
    }
    isp[x]=2;
}
long long sum=0,ans[maxn];
void add(int x)///x是节点编号 
{
    isp[x]++;
    sum+=1ll*v[x]*w[isp[x]];
}
void del(int x)////
{
    sum-=1ll*v[x]*w[isp[x]];
    isp[x]--;
}
bool flag[maxn];
void ap(int x)
{
    flag[x]?del(c[x]):add(c[x]);flag[x]^=1;
}
void up(int id)
{
    //int xx=h[id].x,kk=h[id].k;
    ///cout<<x<<" "<<k<<" "<<c[x]<<" "<<flag[x]<<endl; 
    if(flag[h[id].x])
    {
        ap(h[id].x);
        c[h[id].x]=h[id].k;
        ap(h[id].x);
    }
    else c[h[id].x]=h[id].k;
}
void down(int id)
{
    //int xx=h[id].x,k=h[id].kk;
    if(flag[h[id].x])
    {
        ap(h[id].x);
        c[h[id].x]=h[id].kk;
        ap(h[id].x);
    }
    else c[h[id].x]=h[id].kk;
}
signed main()
{
    n=read();m=read();qq=read();
    //
    for(int i=1;i<=m;i++)v[i]=read();
    for(int i=1;i<=n;i++)w[i]=read();
    //
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        g[u].push_back(v);g[v].push_back(u);
    }
    //
    for(int i=1;i<=n;i++)c[i]=read();
    //
    dfs(1,1);
    for(int i=1;i<=2*n;i++)fa[i]=i;
    //for(int i=1;i<=top;i++)cout<<sta[i]<<" ";cout<<endl;
    for(int i=1;i<=qq;i++)
    {
        int op=read();
        if(op)
        {
            int l=read(),r=read();
            q[++cnt1].l=l,q[cnt1].r=r,q[cnt1].id=cnt1,q[cnt1].p=cnt2;//记录一下在此时刻前最近一次的修改时间 
            son[l].push_back(r);son[r].push_back(l);
            bh[l].push_back(cnt1);bh[r].push_back(cnt1); 
        }
        else 
        {
            int x=read(),k=read();
            h[++cnt2].x=x,h[cnt2].k=k,h[cnt2].kk=c[x],c[x]=h[cnt2].k;
        }
    }
    tarjan(1);
    for(int i=1;i<=cnt1;i++)
    {
        if(st[q[i].l]>st[q[i].r])swap(q[i].l,q[i].r);
        if(q[i].lca==q[i].l||q[i].lca==q[i].r)q[i].l=st[q[i].l],q[i].r=st[q[i].r],q[i].lca=0;
        else q[i].l=ed[q[i].l],q[i].r=st[q[i].r];
    }
    siz=pow(top,0.6657);
    sort(q+1,q+cnt1+1,cmp);
    memset(isp,0,sizeof(isp));
    memset(flag,0,sizeof(flag));ti=cnt2; 
    for(int i=1;i<=cnt1;i++)
    {
        if(q[i].l>q[i].r)swap(q[i].l,q[i].r);
        while(curl>q[i].l)ap(sta[--curl]);
        while(curr<q[i].r)ap(sta[++curr]);
        while(curl<q[i].l)ap(sta[curl++]);
        while(curr>q[i].r)ap(sta[curr--]);
        while(ti<q[i].p)up(++ti);
        while(ti>q[i].p)down(ti--);
        if(q[i].lca)ap(q[i].lca);
        ans[q[i].id]=sum;
        if(q[i].lca)ap(q[i].lca);
        //curl=q[i].l;curr=q[i].r;ti=q[i].p;
    }
    for(int i=1;i<=cnt1;i++)
    cout<<ans[i]<<"\n";
    return 0;
}

|