原文链接https://www.cnblogs.com/zhouzhendong/p/BZOJ3052.html
题目传送门 - BZOJ3052
题目传送门 - UOJ#58
题意
给定一棵树，有 $n$ 个节点。有 $m$ 种颜色，第 $i$ 个节点的颜色为 $c_i$ 。
给定参数 $v_{1},v_2,cdots,v_m$ 和 $w_1,w_2,cdots ,w_n$ ，具有以下意义：
第 $i$ 次遇到颜色为 $j$ 的节点，新得到的收益为 $v_{j} imes w_i$ 。
现在有 $q$ 次操作，操作有以下两种类型：
1. 给定 $x,y$ ，询问一个人从节点 $x$ 走到节点 $y$ 得到的总收益。
2. 给定 $x,y$ ，把节点 $x$ 的颜色改成 $y$ 。
请你对于每一个询问输出结果。
$1leq n,m,qleq 10^5,1leq v_i,w_ileq 10^6 m{Time limit = 8s} $
题解
树上带修莫队模板题。
把树上询问转化成括号序列，变成区间问题。然后上带修莫队。
注意询问的时候的特殊情况，例如 $x$ 和 $y$ 存在子孙或祖先关系时，括号序列区间的取值有所不同。
时间复杂度 $O(n^frac{5}{3})$ 。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int read(){
char ch=getchar();
int x=0;
while (!isdigit(ch))
ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x;
}
const int N=100005;
struct Gragh{
static const int M=N*2;
int cnt,y[M],nxt[M],fst[N];
void clear(){
cnt=0;
memset(fst,0,sizeof fst);
}
void add(int a,int b){
y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;
}
}g;
struct Query{
int L,R,id,LCA;
LL ans;
Query(){}
Query(int _L,int _R,int _id,int _LCA){
L=_L,R=_R,id=_id,LCA=_LCA;
}
}Q[N];
struct Operation{
int x,v1,v2,id;
Operation(){}
Operation(int _x,int _v1,int _v2,int _id){
x=_x,v1=_v1,v2=_v2,id=_id;
}
}O[N];
int n,m,q,Qcnt,Ocnt;
int depth[N],fa[N][20],in[N],out[N],id[N<<1],bID[N<<1],Time;
int v[N],w[N],c[N],dc[N];
int tax[N],opt[N];
void dfs(int x,int pre,int d){
fa[x][0]=pre,depth[x]=d,id[in[x]=++Time]=x;
for (int i=1;i<17;i++)
fa[x][i]=fa[fa[x][i-1]][i-1];
for (int i=g.fst[x];i;i=g.nxt[i])
if (g.y[i]!=pre)
dfs(g.y[i],x,d+1);
id[out[x]=++Time]=x;
}
int LCA(int x,int y){
if (depth[x]<depth[y])
swap(x,y);
for (int i=16;i>=0;i--)
if (depth[x]-(1<<i)>=depth[y])
x=fa[x][i];
if (x==y)
return x;
for (int i=16;i>=0;i--)
if (fa[x][i]!=fa[y][i])
x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
bool cmp(Query a,Query b){
if (bID[a.L]!=bID[b.L])
return bID[a.L]<bID[b.L];
if (bID[a.R]!=bID[b.R])
return bID[a.R]<bID[b.R];
return a.id<b.id;
}
bool cmpid(Query a,Query b){
return a.id<b.id;
}
LL ans=0;
void update(int i){
int x=id[i];
if (!opt[x])
ans+=1LL*v[c[x]]*w[++tax[c[x]]];
else
ans-=1LL*v[c[x]]*w[tax[c[x]]--];
opt[x]^=1;
}
void update_Time(int i){
int x=O[i].x,a=O[i].v1,b=O[i].v2;
if (c[x]!=a)
swap(a,b);
if (opt[x])
ans-=1LL*v[c[x]]*w[tax[c[x]]--];
c[x]=b;
if (opt[x])
ans+=1LL*v[c[x]]*w[++tax[c[x]]];
}
void solve(){
sort(Q+1,Q+Qcnt+1,cmp);
O[0].id=0,O[Ocnt+1].id=q+1;
memset(tax,0,sizeof tax);
memset(opt,0,sizeof opt);
int L=1,R=0,t=0;
for (int i=1;i<=Qcnt;i++){
while (L<Q[i].L)
update(L++);
while (L>Q[i].L)
update(--L);
while (R<Q[i].R)
update(++R);
while (R>Q[i].R)
update(R--);
while (O[t+1].id<Q[i].id)
update_Time(++t);
while (O[t].id>Q[i].id)
update_Time(t--);
Q[i].ans=ans+1LL*v[c[Q[i].LCA]]*w[tax[c[Q[i].LCA]]+1];
}
sort(Q+1,Q+Qcnt+1,cmpid);
}
int main(){
n=read(),m=read(),q=read();
for (int i=1;i<=m;i++)
v[i]=read();
for (int i=1;i<=n;i++)
w[i]=read();
g.clear();
for (int i=1,a,b;i<n;i++){
a=read(),b=read();
g.add(a,b);
g.add(b,a);
}
for (int i=1;i<=n;i++)
dc[i]=c[i]=read();
Time=0;
dfs(1,0,0);
for (int i=1;i<=n*2;i++)
bID[i]=(i-1)/pow(n,0.666);
Qcnt=Ocnt=0;
for (int i=1;i<=q;i++){
int opt=read(),x=read(),y=read();
if (!opt){
O[++Ocnt]=Operation(x,dc[x],y,i);
dc[x]=y;
}
else {
if (in[x]>in[y])
swap(x,y);
int lca=LCA(x,y);
if (x==lca)
Q[++Qcnt]=Query(in[x],in[y],i,0);
else
Q[++Qcnt]=Query(out[x],in[y],i,lca);
}
}
solve();
for (int i=1;i<=Qcnt;i++)
printf("%lld
",Q[i].ans);
return 0;
}