是否 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;
}