树上带修莫队 全WA求调

rt

连样例都没过qwq

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
inline int read(){
    int x=0;
    bool f=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') f=0;
        ch=getchar();
    }
    while(ch<='9'&&ch>='0'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f?x:-x;
}
struct A{
    int ne,v;
}a[2000009];
struct B{
    int l,r,id,lc,tim;
}b[2000009];
struct C{
    int x,y;
}xg[2000009];
int h[1000009];
int n,m,q,siz,num,numb,cnt_ask,cnt_tim,now_tim,cnt;
long long now;
int v[1000009];
int w[1000009];
int t[1000009];
int c[1000009];
int fa[1000009];
int de[1000009];
int sz[1000009];
int sn[1000009];
int tp[1000009];
int ord[2000009];
int fir[1000009];
int sec[1000009];
int bel[1000009];
int ans[1000009];
bool vis[2000009];
inline bool cmp(B a,B b){
    return bel[a.l]==bel[b.l]?(bel[a.r]==bel[b.r]?a.tim<b.tim:a.r<b.r):a.l<b.l;
}
inline void add(int u,int v){
    a[++num].ne=h[u];
    h[u]=num;
    a[num].v=v;
    return;
}
inline void dfs1(int x){
    sz[x]=1;
    ord[++cnt]=x;
    fir[x]=cnt;
    int maxx=0;
    for(int i=h[x];i;i=a[i].ne){
        int v=a[i].v;
        if(de[v])
            continue;
        fa[v]=x;
        de[v]=de[x]+1;
        dfs1(v);
        sz[x]+=sz[v];
        if(sz[v]>maxx){
            maxx=sz[v];
            sn[x]=v;
        }
    }
    ord[++cnt]=x;
    sec[x]=cnt;
    return;
}
inline void dfs2(int x,int top_){
    tp[x]=top_;
    if(sn[x])
        dfs2(sn[x],top_);
    for(int i=h[x];i;i=a[i].ne){
        int to=a[i].v;
        if(to==fa[x]||to==sn[x])
            continue;
        dfs2(to,to);
    }
    return;
}
inline int lca(int x,int y){
    while(tp[x]!=tp[y]){
        if(de[tp[x]]<de[tp[y]])
            swap(x,y);
        x=fa[tp[x]];
    }
    if(de[x]>de[y])
        swap(x,y);
    return x;
}
inline void work(int x){
    if(vis[x]){
        now-=w[c[x]]*v[t[c[x]]];
        t[c[x]]--;
    }
    else{
        t[c[x]]++;
        now+=w[c[x]]*v[t[c[x]]];
    }
    vis[x]^=1;
    return;
}
int main(){
    //
    n=read();
    m=read();
    q=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();
        int to=read();
        add(u,to);
        add(to,u);
    }
    for(int i=1;i<=n;++i)
        c[i]=read();
    de[1]=1;
    dfs1(1);
    dfs2(1,1);
    siz=pow(cnt,2.0/3.0);
    numb=ceil((double)cnt/siz);
    for(int i=1;i<=numb;++i)
        for(int j=(i-1)*siz+1;j<=min(cnt,i*siz);++j)
            bel[j]=i;
    for(int i=1;i<=q;++i){
        int op=read();
        if(op&1){
            b[++cnt_ask].l=read();
            b[cnt_ask].r=read();
            b[cnt_ask].id=cnt_ask;
            b[cnt_ask].tim=cnt_tim;
            if(fir[b[cnt_ask].l]>fir[b[cnt_ask].r])
                swap(b[cnt_ask].l,b[cnt_ask].r);
            int lc=lca(b[cnt_ask].l,b[cnt_ask].r);
            if(b[cnt_ask].l==lc){
                b[cnt_ask].l=fir[b[cnt_ask].l];
                b[cnt_ask].r=fir[b[cnt_ask].r];
            }
            else{
                b[cnt_ask].l=sec[b[cnt_ask].l];
                b[cnt_ask].r=fir[b[cnt_ask].r];
                b[cnt_ask].lc=lc;
            }
        }
        else{
            xg[++cnt_tim].x=read();
            xg[cnt_tim].y=read();
        }
    }
    sort(b+1,b+1+cnt_ask,cmp);
    int l=1,r=0;
    for(int i=1;i<=cnt_ask;++i){
        while(r<b[i].r) work(ord[++r]);
        while(r>b[i].r) work(ord[r--]);
        while(l<b[i].l) work(ord[l++]);
        while(l>b[i].l) work(ord[--l]);
        while(b[i].tim>now_tim){
            now_tim++;
            if(vis[xg[now_tim].x]){
                now-=w[t[c[xg[now_tim].x]]]*v[c[xg[now_tim].x]];
                t[c[xg[now_tim].x]]--;
                t[xg[now_tim].y]++;
                now+=w[t[xg[now_tim].y]]*v[xg[now_tim].y];
            }
            swap(c[xg[now_tim].x],xg[now_tim].y);
        }
        while(b[i].tim<now_tim){
            if(vis[xg[now_tim].x]){
                now-=w[t[c[xg[now_tim].x]]]*v[c[xg[now_tim].x]];
                t[c[xg[now_tim].x]]--;
                t[xg[now_tim].y]++;
                now+=w[t[xg[now_tim].y]]*v[xg[now_tim].y];
            }
            swap(c[xg[now_tim].x],xg[now_tim].y);
            now_tim--;
        }
        if(b[i].lc) work(b[i].lc);
        ans[b[i].id]=now;
        if(b[i].lc) work(b[i].lc);
    }
    for(int i=1;i<=cnt_ask;++i)
        cout<<ans[i]<<'\n';
    return 0;
}