```cpp
//洛谷 P4074 糖果公园
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int Read()
{
int i=0,f=1;
char c;
for(c=getchar();c!='-'&&!isdigit(c);c=getchar());
if(c=='-')
{
f=-1;
c=getchar();
}
for(;isdigit(c);c=getchar())
i=(i<<1)+(i<<3)+c-'0';
return i*f;
}
const int N=100005,M=100005,Q=100005;
int n,m,q,s,cnt,sum;
int a[Q],b[Q],c[M],v[N],w[N],id[N],ans[Q],cou[N],val[Q],last[Q],type[Q];
int bottom,top,dep[N],fa[N][18];
int t=0,first[N],to[2*N],next[2*N];
bool sta[N];
struct node
{
int x,y,bl,br,num;
}query[Q];
int cmp(const node &p,const node &q)
{
if(p.bl!=q.bl) return p.bl<q.bl;
if(p.br!=q.br) return p.br<q.br;
return p.num<q.num;
}
void add(int x,int y)
{
next[++t]=first[x];first[x]=t;to[t]=y;
next[++t]=first[y];first[y]=t;to[t]=x;
}
void dfs(int x,int father)
{
int i,y,bottom=top;
dep[x]=dep[father]+1;
for(i=0;fa[x][i];++i)
fa[x][i+1]=fa[fa[x][i]][i];
for(i=first[x];i;i=next[i])
{
y=to[i];
if(y==father)
continue;
dfs(y,x);
if(top-bottom>=s)
{
sum++;
while(top>bottom)
id[sta[top--]]=sum;
}
}
sta[++top]=x;
}
int lca(int x,int y)
{
int i;
if(dep[x]<dep[y]) swap(x,y);
for(i=17;i>=0;--i)
if(dep[fa[x][i]]>=dep[y])
x=fa[x][i];
if(x==y) return x;
for(i=17;i>=0;--i)
{
if(fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
void rev(int x)
{
cnt-=w[cou[c[x]]]*v[c[x]];
sta[x]?--cou[c[x]]:++cou[c[x]];
sta[x]=!sta[x];
cnt+=w[cou[c[x]]]*v[c[x]];
}
void solve(int x,int y)
{
int z=lca(x,y);
while(x!=z) rev(x),x=fa[x][0];
while(y!=z) rev(y),y=fa[y][0];
}
void modify(int x,int y)
{
if(!sta[x])
{
c[x]=y;
return;
}
rev(x);
c[x]=y;
rev(x);
}
int upt(int tarT,int curT)
{
while(curT<tarT)
{
curT++;
if(!type[curT])
modify(a[curT],b[curT]);
}
while(curT>tarT)
{
if(!type[curT])
modify(a[curT],last[curT]);
curT--;
}
}
int main()
{
int i,z,tot=0;
n=Read();m=Read();q=Read();
s=pow(n,2.0/3.0);
for(i=1;i<=m;++i) v[i]=Read();
for(i=1;i<=n;++i) w[i]=Read();
for(i=2;i<=n;++i) w[i]+=w[i-1];
for(i=1;i<n;++i) add(Read(),Read());
for(i=1;i<=n;++i) val[i]=c[i]=Read();
dfs(1,0);
while(top)
id[sta[top--]]=sum;
for(i=1;i<=q;++i)
{
scanf("%d%d%d",&type[i],&a[i],&b[i]);
if(type[i])
{
tot++;
if(id[a[i]]>id[b[i]]) swap(a[i],b[i]);
query[tot].x=a[i];
query[tot].y=b[i];
query[tot].bl=id[a[i]];
query[tot].br=id[b[i]];
query[tot].num=i;
}
else
{
last[i]=val[a[i]];
val[a[i]]=b[i];
}
}
sort(query+1,query+tot+1,cmp);
for(i=1;i<=tot;++i)
{
upt(query[i].num,query[i-1].num);
solve(query[i].x,query[i-1].x);
solve(query[i].y,query[i-1].y);
z=lca(query[i].x,query[i].y);
rev(z);
ans[query[i].num]=cnt;
rev(z);
}
for(i=1;i<=q;++i)
if(type[i])
printf("%d\n",ans[i]);
return 0;
}
```
by forever_dreams @ 2018-07-01 23:11:36
唔，你可以看看lyh的pdf啊
by ldxcaicai @ 2018-07-02 00:34:55
@[ldxoi](/space/show?uid=47765)
唔
谢谢
by forever_dreams @ 2018-07-02 07:42:18