蒟蒻求教大佬，一个点都没过呜呜呜

我是用的树剖lca，样例过了的。

#include <cstdio>
#include <iostream> 
#include <algorithm>
#include <cstring>
#include <cmath>
#define ll long long 
using namespace std;
const int maxn=100010;
const int maxm=1e6+10;
int n,m,ques,s,tim,anss;
struct nmsl{
    int l,r,bl,id,lca,times,ans;
    inline bool operator<(const nmsl &ikunkun)const
    {
        if(bl==ikunkun.bl)
            return r<ikunkun.r || r==ikunkun.r && times<ikunkun.times;
        else 
            return bl<ikunkun.bl;
    }
}q[maxn];//以l所属的块为第一关键字，r为第二关键字，times为第三关键字排序
struct cxknmsl{
    int x,y;
}history[maxn];//存储改变语句
int v[maxn],w[maxn],c[maxn],first[maxn*2],next[maxn*2],to[maxn*2],tot;
int deep[maxn],fa[maxn],son[maxn],size[maxn],start[maxn],end[maxn],oula[maxn];
int cxk[maxn],happen[maxm],used[maxm],top[maxn];
int read()
{
    int f=1,x=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

void add(int x,int y)
{
    tot++;
    next[tot]=first[x];
    first[x]=tot;
    to[tot]=y;
}

void dfs1(int now,int father)
{
    size[now]=1;
    fa[now]=father;
    start[now]=++tot;oula[tot]=now;
    for(int i=first[now];i;i=next[i])
    {
        int x=to[i];
        if(deep[x]) continue;
        deep[x]=deep[now]+1;
        dfs1(x,now);
        size[x]+=size[now];
        if(size[son[now]]<size[x])
            son[now]=x;
    }
    end[now]=++tot;oula[tot]=now;
}

void dfs2(int now,int fatop)
{
    top[now]=fatop;
    if(son[now])
        dfs2(son[now],fatop);
    for(int i=first[now];i;i=next[i])
    {
        int x=to[i];
        if(x==fa[now] || x==son[now])
            continue;
        dfs2(x,x);
    }
}
//两个dfs解决树剖与欧拉序（好像不是欧拉序但我不管了）
int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(deep[top[x]]<deep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    return deep[x]<deep[y]?x:y;
}
//找lca
void delet(int ilovekk)
{

    anss-=w[happen[ilovekk]]*ilovekk;
    happen[ilovekk]--;
    anss+=w[happen[ilovekk]]*ilovekk;
}
//删除
void add(int ilovekk)
{
    anss-=w[happen[ilovekk]]*ilovekk;
    happen[ilovekk]++;
    anss+=w[happen[ilovekk]]*ilovekk;
}
//加入
void Add(int x)
{
    used[x]?delet(c[x]):add(c[x]);
    used[x]^=1;
}
//判断是否在欧拉序中出现两次
int main()
{
    n=read();m=read();ques=read();
    s=pow(n,2.0/3.0)*0.5;  
    for(int i=1;i<=m;i++)
        v[i]=read();
    for(int i=1;i<=n;i++)
        w[i]=read();
    for(int i=2;i<=n;i++)
        w[i]+=w[i-1];
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        x=read();y=read();
        add(x,y);add(y,x);
    }
    for(int i=1;i<=n;i++)
        c[i]=read();
    for(int i=1;i<=n;i++)
        c[i]=v[c[i]];
    deep[1]=1;tot=0;
    dfs1(1,0);
    dfs2(1,1);
    tim=0;tot=0;
    for(int i=1;i<=ques;i++)
    {
        int l,r,lca,type;
        type=read();l=read();r=read();
        if(type==1)
        {
            if(start[l]>start[r])
                swap(l,r);
            lca=LCA(l,r);
            if(lca==l)
            {
                q[++tot].id=tot;
                q[tot].l=start[l];
                q[tot].r=start[r];
                q[tot].bl=(q[tot].l-1)/s+1;
                q[tot].times=tim;
            }
            else 
            {
                q[++tot].id=tot;
                q[tot].l=end[l];
                q[tot].r=start[r];
                q[tot].bl=(q[tot].l-1)/s+1;
                q[tot].times=tim;
                q[tot].lca=lca;
            }
        }
        else
        {
            tim++;
            history[tim].x=l;
            history[tim].y=v[r];
        }
    }
    sort(q+1,q+1+tot);
    int timenow=0,l=0,r=0;anss=0;
    int flag=0;
   //蒟蒻的可爱莫队
    for(int i=1;i<=tot;i++)
    {
        while(timenow<q[i].times)
        {
            timenow++;
            if(used[history[timenow].x]==1)
                Add(history[timenow].x),flag=1;
            int change=c[history[timenow].x];
        c[history[timenow].x]=history[timenow].y;
            history[timenow].y=change;
            if(flag==1)
                Add(history[timenow].x),flag=0;
        }
        while(timenow>q[i].times)
        {
            if(used[history[timenow].x]==1)
                Add(history[timenow].x),flag=1;
            int change=c[history[timenow].x];
            c[history[timenow].x]=history[timenow].y;
            history[timenow].y=change;
            if(flag==1)
                Add(history[timenow].x),flag=0;
            timenow--;
        }//处理上个询问时间与这个询问时间
      //接下来就是普通树上莫队
        while(l>q[i].l)
        {
            l--;
            Add(oula[l]);
        }
        while(l<q[i].l)
        {
            Add(oula[l]);
            l++;
        }
        while(r>q[i].r)
        {
            Add(oula[r]);
            r--;
        }
        while(r<q[i].r)
        {
            r++;
            Add(oula[r]);
        }
        if(q[i].lca)
            Add(q[i].lca);
        q[i].ans=anss;
        if(q[i].lca)
            Add(q[i].lca);
    }
   //用cxk存储答案
    for(int i=1;i<=tot;i++)
        cxk[q[i].id]=q[i].ans;
    for(int i=1;i<=tot;i++)
        printf("%d\n",cxk[i]);//输出
    return 0;
}