蒟蒻不会分块求条

是否 sort 一样慢

sort

不 sort

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

#define N 100005
#define M 100005

int n,m,q;
vector<int> tree[N];
long long v[M],w[N];
int c[N],cnt[N];
int depth[N],fa[N];
int bsize,btot;
int from[N];
int stack[N],top;
struct change{int x,y;}cs[N];int ctot;
struct query{int l,r,times,id;}qs[N];int qtot;
bool flag[N];
long long answer[N];

inline int read()
{
    long long x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')f=c=='-'?-1:1,c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return x*f;
}

void init(int u)
{
    int ftop=top;
    for(int v:tree[u])
        if(v!=fa[u])
        {
            depth[v]=depth[u]+1;
            fa[v]=u;
            init(v);
            if(top-ftop>=bsize)
            {
                ++btot;
                while(top>ftop)
                    from[stack[top--]]=btot;
            }
        }
    stack[++top]=u;
}

void add(int type,long long &ans){ans+=v[type]*w[++cnt[type]];}

void del(int type,long long &ans){ans-=v[type]*w[cnt[type]--];}

void chg(int u,long long &ans){if(flag[u])del(c[u],ans),flag[u]=0;else add(c[u],ans),flag[u]=1;}

void modi(change &cg,long long &ans)
{
    if(flag[cg.x])
    {
        del(c[cg.x],ans);
        add(cg.y,ans);
    }
    c[cg.x]^=cg.y;
    cg.y^=c[cg.x];
    c[cg.x]^=cg.y;
}

signed main()
{
    // scanf("%d%d%d",&n,&m,&q);
    n=read();m=read();q=read();
    for(int i=1;i<=m;++i)
        // scanf("%lld",&v[i]);
        v[i]=read();
    for(int i=1;i<=n;++i)
        // scanf("%lld",&w[i]);
        w[i]=read();
    for(int i=1;i<n;++i)
    {
        int u,v;
        // scanf("%d%d",&u,&v);
        u=read();v=read();
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for(int i=1;i<=n;++i)
        // scanf("%d",&c[i]);
        c[i]=read();
    bsize=pow(n,2.0/3);
    init(1);
    ++btot;
    while(top)
        from[stack[top--]]=btot;
    for(int i=1;i<=q;++i)
    {
        int op;
        // scanf("%d",&op);
        op=read();
        if(op==0)
            // scanf("%d%d",&cs[ctot].x,&cs[++ctot].y);
            cs[++ctot].x=read(),cs[ctot].y=read();
        else
            // scanf("%d%d",&qs[qtot].l,&qs[++qtot].r),
            qs[++qtot].l=read(),qs[qtot].r=read(),
            qs[qtot].times=ctot,
            qs[qtot].id=qtot;
    }
    sort(qs+1,qs+qtot+1,[](query a,query b){return from[a.l]<from[b.l]||from[a.l]==from[b.l]&&a.times<b.times;}); // 这一行
    long long l=1,r=1,times=0,ans=0;
    for(int i=1;i<=qtot;++i)
    {
        int fl=qs[i].l,fr=qs[i].r;
        int tl=fl,tr=fr;

        chg(fl,ans);
        chg(fr,ans);
        while(depth[fl]>depth[fr])
            fl=fa[fl],
            chg(fl,ans);
        while(depth[fr]>depth[fl])
            fr=fa[fr],
            chg(fr,ans);
        while(fl!=fr)
            fl=fa[fl],
            chg(fl,ans),
            fr=fa[fr],
            chg(fr,ans);

        chg(l,ans);
        chg(r,ans);
        while(depth[l]>depth[r])
            l=fa[l],
            chg(l,ans);
        while(depth[r]>depth[l])
            r=fa[r],
            chg(r,ans);
        while(l!=r)
            l=fa[l],
            chg(l,ans),
            r=fa[r],
            chg(r,ans);

        while(times<qs[i].times)
            modi(cs[++times],ans);
        while(times>qs[i].times)
            modi(cs[times--],ans);

        l=tl;r=tr;
        answer[qs[i].id]=ans+v[c[fl]]*w[cnt[c[fl]]+1];
    }
    for(int i=1;i<=qtot;++i)
        printf("%lld\n",answer[i]);
    return 0;
}