蒟蒻求调代码

嘤嘤嘤，调不出来…

样例过了，20分…

#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
#define int long long
const int N=1e6+10;
struct edge{
    int from,to;
    int nxt;
};
struct quest{
    int l,r;
    int tim;
    int lca;
    int pos;
};
struct node{
    int old_val,new_val;
    int pos;
};
edge e[N];
quest q[N];
node c[N];
int last[N];
int f[N][30],dep[N];
int rev[N],st[N],ed[N];
int blo[N],lm[N],rm[N];
int a[N],b[N],v[N],w[N],cnt[N],used[N],res[N];
int num,tot,block;
inline bool cmp(quest x,quest y){
    if(blo[x.l]!=blo[y.l])
        return blo[x.l]<blo[y.l];
    else if(blo[x.r]!=blo[y.r])
        return blo[x.r]<blo[y.r];
    else
        return x.tim<y.tim;
}
inline void add(int from,int to){
    tot++;
    e[tot].from=from;
    e[tot].to=to;
    e[tot].nxt=last[from];
    last[from]=tot;
}
void dfs(int u,int fa){
    rev[++num]=u;
    st[u]=num;
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=20;i++)
        f[u][i]=f[f[u][i-1]][i-1];
    for(int i=last[u];i;i=e[i].nxt)
        if(e[i].to!=fa)
            dfs(e[i].to,u);
    rev[++num]=u;
    ed[u]=num;
}
int get_lca(int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);
    for(int i=20;i>=0;i--)
        if(dep[f[x][i]]>=dep[y])
            x=f[x][i];
    if(x==y)
        return x;
    for(int i=20;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
inline void add_ans(int x,int &ans){
    cnt[a[x]]++;
    ans+=v[a[x]]*w[cnt[a[x]]];
}
inline void del_ans(int x,int &ans){
    ans-=v[a[x]]*w[cnt[a[x]]];
    cnt[a[x]]--;
}
inline void change(int x,int &ans){
    used[x]?del_ans(x,ans):add_ans(x,ans);
    used[x]^=1;
}
signed main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++)
        cin>>v[i];
    for(int i=1;i<=n;i++)
        cin>>w[i];
    int x,y;
    for(int i=1;i<=n-1;i++){
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    block=pow(2*n,1/3.0);
    for(int i=1;i<=block;i++){
        lm[i]=(i-1)*block*block+1;
        rm[i]=i*block*block;
    }
    rm[block]=2*n;
    for(int i=1;i<=block;i++)
        for(int j=lm[i];j<=rm[i];j++)
            blo[j]=i;
    int opt,pos,tim=0;
    for(int i=1;i<=k;i++){
        cin>>opt;
        if(!opt){
            ++tim;
            cin>>c[tim].pos>>c[tim].new_val;
            c[tim].old_val=b[c[tim].pos];
            b[c[tim].pos]=c[tim].new_val;
        }
        else{
            pos=i-tim;
            cin>>q[pos].l>>q[pos].r;
            q[pos].pos=pos;
            q[pos].tim=tim;
            q[pos].lca=get_lca(q[pos].l,q[pos].r);
            if(st[q[i].l]>st[q[pos].r])
                swap(st[q[pos].l],st[q[pos].r]);
            if(q[pos].lca==q[pos].l){
                q[pos].lca=0;
                q[pos].l=st[q[pos].l];
                q[pos].r=st[q[pos].r];
            }
            else{
                q[pos].l=ed[q[pos].l];
                q[pos].r=st[q[pos].r];
            }
        }
    }
    k-=tim;
    sort(q+1,q+k+1,cmp);
    int l=1,r=0;
    int ans=0;
    tim=0;
    for(int i=1;i<=k;i++){
        while(l<q[i].l)
            change(rev[l++],ans);
        while(r<q[i].r)
            change(rev[++r],ans);
        while(l>q[i].l)
            change(rev[--l],ans);
        while(r>q[i].r)
            change(rev[r--],ans);
        if(q[i].lca)
            change(q[i].lca,ans);
        while(tim<q[i].tim){
            tim++;
            pos=c[tim].pos;
            if(used[pos]){
                ans-=v[a[pos]]*w[cnt[a[pos]]];
                cnt[a[pos]]--;
            }
            a[pos]=c[tim].new_val;
            if(used[pos]){
                cnt[a[pos]]++;
                ans+=v[a[pos]]*w[cnt[a[pos]]];
            }
        }
        while(tim>q[i].tim){
            pos=c[tim].pos;
            if(used[pos]){
                ans-=v[a[pos]]*w[cnt[a[pos]]];
                cnt[a[pos]]--;
            }
            a[pos]=c[tim].old_val;
            if(used[pos]){
                cnt[a[pos]]++;
                ans+=v[a[pos]]*w[cnt[a[pos]]];
            }
            tim--;
        }
        res[q[i].pos]=ans;
        if(q[i].lca)
            change(q[i].lca,ans);
    }
    for(int i=1;i<=k;i++)
        cout<<res[i]<<'\n';
}