#include<bits/stdc++.h>
using namespace std;
#define hh cout<<'\n'
#define all(x) (x).begin(),(x).end()
typedef long long ll;

const int N=4e5+5;
struct SBQUERY{int q[6];}query[N];
// vector<int> e[N];
struct node{int v,nxt,to;}e[N];
int head[N],ctot=0;
void add(int u,int v)
{
	e[++ctot].to=v;
	e[ctot].nxt=head[u];
	head[u]=ctot;
}

int C[N],V[N],W[N];
int tot,ord[N],fir[N],las[N],dep[N],fa[N];
int belong[N],cntq,cntm,modify[N][2],cnt[N];
bool tag[N];
ll ans[N];
int mindep[N<<1][30];

void dfs(int u,int dad)
{
	fa[u]=dad;
	ord[++tot]=u;
	fir[u]=tot;
	dep[u]=dep[dad]+1;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v!=dad)
			dfs(v,u);
	}
	ord[++tot]=u;
	las[u]=tot;
}

inline int lca(int x,int y)
{
    if(x==y)return x;
    if(fir[x]>fir[y])swap(x,y);
    if(las[y]<las[x])return x;
    x=las[x],y=fir[y];
    int len=__lg(y-x+1);
    return fa[ dep[mindep[x][len]]<dep[mindep[y-(1ll<<len)+1][len]]?
                   mindep[x][len] :    mindep[y-(1ll<<len)+1][len]  ];
}

ll res=0;

inline void Modify(int x)//带修套路：对编号为x的点操作
{
	if(!tag[x])res+=1ll*W[++cnt[C[x]]]*V[C[x]];
	else res-=1ll*W[cnt[C[x]]--]*V[C[x]];
	tag[x]=!tag[x];
};

inline void modi(int t,int ql,int qr)
{
	int pos=modify[t][0];//获得修改的点编号
	if(tag[pos])//ql-qr区间里存在被修改的点
	{
		Modify(pos);//删除贡献
		swap(C[pos],modify[t][1]);
		Modify(pos);//增加贡献
	}
	else swap(C[pos],modify[t][1]);			
};

void solve()
{
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++)cin>>V[i];
	for(int i=1;i<=n;i++)cin>>W[i];
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}

	dfs(1,0);

	for(int i=1;i<=tot;i++)
        mindep[i][0]=ord[i];

    for(int i=1;i<30;i++)
        for(int j=1;j<=tot;j++)
            if(j+(1ll<<i)-1<=tot)
                mindep[j][i]=dep[mindep[j][i-1]]<dep[mindep[j+(1ll<<(i-1))][i-1]]
            				?    mindep[j][i-1] :    mindep[j+(1ll<<(i-1))][i-1];

	for(int i=1;i<=n;i++)cin>>C[i];
	for(int i=1;i<=q;i++)
	{
		int op,x,y;
		cin>>op>>x>>y;
		if(op==0)
		{
			modify[++cntm][0]=x;
			modify[cntm][1]=y;
		}
		else
		{
			if(fir[x]>fir[y])swap(x,y);
			if(las[y]<las[x])
			{
				query[++cntq].q[0]=fir[x]+1;
				query[cntq].q[1]=fir[y];
			}
			else
			{
				query[++cntq].q[0]=las[x];
				query[cntq].q[1]=fir[y];
			}
			query[cntq].q[2]=cntm,query[cntq].q[3]=cntq;
			query[cntq].q[4]=x,query[cntq].q[5]=y;
		}
	}

	int siz=pow(n,2.0/3);
	int bsiz=(n+siz-1)/siz;

	for(int i=1;i<=n;i++)
		belong[i]=(i-1)/siz+1;

	sort(query+1,query+1+cntq,[&](auto a,auto b)
	{
		return belong[a.q[0]]!=belong[b.q[0]]
		?belong[a.q[0]]<belong[b.q[0]]
		:(belong[a.q[1]]!=belong[b.q[1]]
		?belong[a.q[1]]<belong[b.q[1]]
		:a.q[2]<b.q[2]);//分块排序
	});

	for(int l=1,r=0,t=0,i=1;i<=cntq;i++)
	{
		int ql=query[i].q[0],qr=query[i].q[1],qt=query[i].q[2];
		while(l < ql) Modify(ord[l++]);//注意传参是编号
		while(l > ql) Modify(ord[--l]);
		while(r < qr) Modify(ord[++r]);
		while(r > qr) Modify(ord[r--]);
		while(t < qt) modi(++t,ql,qr);
		while(t > qt) modi(t--,ql,qr);
		Modify(lca(query[i].q[4],query[i].q[5]));
		ans[query[i].q[3]]=res;
		Modify(lca(query[i].q[4],query[i].q[5]));
	}

	for(int i=1;i<=cntq;i++)
		cout<<ans[i]<<'\n';
}

signed main()
{
    // freopen("1.in","r",stdin);
    // freopen("my.out","w",stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);std::cout.tie(0);
	int T=1;
	while(T--)
		solve();
	return 0;
}

（lca是基于欧拉序的）

这代码哪里会常数比较大呢