求助WATTTTTTTTT，莫队qwq

样例过了，然而……

// Problem: P4074 [WC2013] 糖果公园
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4074
// Memory Limit: 500 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <stdio.h>
#include <string.h> 
#include <algorithm>
#include <queue>
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
//#include <bits/extc++.h>
inline int read()
{
    int num=0,f=1;char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>47&&c<58)num=num*10+(c^48),c=getchar();
    return num*f;
}
#define edge e
#define p nxt
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
#define log(x) Log[x]
struct Edge
{
    int v, p;
}edge[1000086];
int Log[500086], h[500086], cnt = 1;
inline void iniLog(int n)
{
    for (int i = 1; i <= n; i++)Log[i] = Log[i - 1] + (!((1 << Log[i - 1]) ^ i));
}
void addedge(int u, int v)
{
    edge[cnt] = { v, h[u] };
    h[u] = cnt++;
}
int pre[500086][20], depth[500086];
void dfs(int, int);
int LCA(int, int);
int L[200005],R[200005],cc;
int a[1000005],c[1000005],g[1000005],pigstd[1000005];
//__gnu_pbds::gp_hash_table<int,int> b;
int b[100005];
void dfsdfs(int u,int fa)
{
    L[u]=++cc;
    pigstd[cc]=u;
    a[cc]=g[u];
    for(int i=h[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v!=fa)dfsdfs(v,u);
    }
    R[u]=++cc;
    pigstd[cc]=u;
    a[cc]=g[u];
}
int ans; 
const int B=1700;
struct qaq{
    int l,r,i,lB,type,rB;
    bool operator<(const qaq& b)const
    {
        //return (lB==b.lB)?(((lB)&1)?r<b.r:r>b.r):l<b.l;
        if(lB^b.lB)return lB<b.lB;
        if(rB^b.rB)return rB<b.rB;
        return i<b.i;
    }
}q[1000005];
int w[100005];
#define rmv_Macesuted_Keai(k) ans-=w[b[a[k]]--]*a[k]
#define add_Macesuted_Keai(k) ans+=w[++b[a[k]]]*a[k]
int vis[100005];
inline void swap(int& a,int &b)
{
    a^=b^=a^=b;
}
#define add rmv
inline void add(int x)
{
    if(vis[pigstd[x]])rmv_Macesuted_Keai(x);
    else add_Macesuted_Keai(x);
    vis[pigstd[x]]^=1;
//  odl(ans);
}
#define dep depth
int tmp[100005],upd[100005],val[100005];
int main()
{ 
    int x, y, n = read(), m = read(),qqqwwwqqq=read(),s=1, qwq = n - 1;
    //for(int i=1;i<=n;i++)g[i]=read();
    iniLog(n+n + 1);
    for(int i=1;i<=m;i++)tmp[i]=read();
    for(int i=1;i<=n;i++)w[i]=read();
    while (qwq--)
    {
        int x=read(),y=read();
        addedge(x,y);
        addedge(y, x);
    }
    dfs(s,0);
    dfsdfs(s,0);
    for(int i=1;i<=n;i++)//a[i]=tmp[read()],odb(a[i]);puts("");
    {
        int x=read();
        a[L[i]]=a[R[i]]=tmp[x];
    }
    for(int i=1;i<=qqqwwwqqq;i++)
    {
        q[i].i=i;
        int op=read();
        int u=read(),v=read();
        if(op)
        {
            if(L[u]>L[v])u^=v^=u^=v;
            int lca=LCA(u,v);
            if(lca==u)
            {
                q[i].l=L[u],q[i].r=L[v],q[i].lB=q[i].l/B;
            }
            else
            {
                q[i].type=lca,q[i].l=R[u],q[i].r=L[v],q[i].lB=q[i].l/B;
            }
            q[i].rB=q[i].r/B;
        }
        else
        {
            upd[i]=u,val[i]=tmp[v];
            q[i].l=-1;
        }
    }
    //for(int i=1;i<=cc;i++)printf("%d ",a[i]);puts("");
    std::sort(q+1,q+1+qqqwwwqqq);
    register int cl=1,cr=0,ct=0;
    for(register int i=1;i<=qqqwwwqqq;i++)
    {
        int &La=q[i].l,&Ra=q[i].r,&t=q[i].i;
//      odp(La,Ra);
        if(La==-1)continue;
        //printf("%d %d %d\n",La,Ra,q[i].type);
        while(cl>La)add(--cl);
        while(cr<Ra)add(++cr);
        while(cl<La)rmv(cl++);
        while(cr>Ra)rmv(cr--);
        while(ct<t)
        {
            ct++;
            if(upd[ct]==0)continue;
            int pos=upd[ct],v=val[ct],f=0;
            if(cl<=L[pos]&&L[pos]<=cr)rmv_Macesuted_Keai(L[pos]),f|=1;
            if(cl<=R[pos]&&R[pos]<=cr)rmv_Macesuted_Keai(R[pos]),f|=2;
//          a[pos]=tmp[y];
            swap(a[L[pos]],val[ct]);
            a[R[pos]]=a[L[pos]];
            if(cl<=L[pos]&&L[pos]<=cr)add_Macesuted_Keai(L[pos]),f|=1;
            if(cl<=R[pos]&&R[pos]<=cr)add_Macesuted_Keai(R[pos]),f|=2;
        }
        while(ct>t)
        {
            if(upd[ct]==0)continue;
            int pos=upd[ct],v=val[ct],f=0;
            if(cl<=L[pos]&&L[pos]<=cr)rmv_Macesuted_Keai(L[pos]),f|=1;
            if(cl<=R[pos]&&R[pos]<=cr)rmv_Macesuted_Keai(R[pos]),f|=2;
//          a[pos]=tmp[y];
            swap(a[L[pos]],val[ct]);
            a[R[pos]]=a[L[pos]];
            if(cl<=L[pos]&&L[pos]<=cr)add_Macesuted_Keai(L[pos]),f|=1;
            if(cl<=R[pos]&&R[pos]<=cr)add_Macesuted_Keai(R[pos]),f|=2;
            ct--;
        }
        if(q[i].type)
        {
            rmv(L[q[i].type]);
            c[q[i].i]=ans;
            rmv(L[q[i].type]);
        }
        else c[q[i].i]=ans;
    }
    for(int i=1;i<=qqqwwwqqq;i++)if(c[i])printf("%d\n",c[i]);
    return 0;
}
void dfs(int s, int f)
{
    *pre[s] = f, depth[s] = depth[f] + 1;
    for (int i = 1; i <= log(depth[s]); i++)pre[s][i] = pre[pre[s][i - 1]][i - 1];
    for (int i = h[s]; i; i = edge[i].p)if (edge[i].v != f)dfs(edge[i].v, s);
}
#define e edge
#define d depth
int LCA(int u, int v)
{
    if (d[u] < d[v])swap(u, v);
    while (d[u] > d[v])u = pre[u][log(d[u] - d[v]) - 1];
    if (!(u^v)) return u;
    for (int q = log(depth[u]) - 1; ~q; q--)
        if (pre[u][q] ^ pre[v][q])u = pre[u][q], v = pre[v][q];
    return *pre[u];
}
/*
1 114514 114514 998244353 998244353 1919810 1919810 114514 114514 1

*/