题目：
AtCoder - ABC133F：Colorful Tree
题意：
给定一颗树，每条边有一个颜色和长度，现在有 Q 次独立的查询，每次先将 u 到 v 的路径上颜色为 x 的边长度修改成 y，然后查询u 到 v 的路径长度
分析：
（1）时限给得比较大，最自然的想法是树上莫队，大致过程是先对树跑一个括号序列，然后就可以像普通莫队那样搞了，但是我们需要维护的是边的信息，于是乎将边权下沉转换为点权，这样也不用在考虑 lca 的贡献了，没什么细节
代码：
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
const int maxn = 2e5+15;
int n,Q,a,b,c,d,cnt,head[maxn],ans[maxn];
struct edge{
int to,nxt,col,len;
}e[maxn<<1];
struct query{
int l,r,x,y,id;
}q[maxn<<1];
pii p[maxn];
inline void add(int u,int v,int c,int d){
e[++cnt] = (edge){v,head[u],c,d};
head[u] = cnt;
}
int dp[maxn][20],deep[maxn],st[maxn],ed[maxn],tot,A[maxn<<1];
void dfs(int x,int fa,int depth){
A[++tot] = x; st[x] = tot; deep[x] = depth;
for(int i = head[x];i > 0;i = e[i].nxt){
int v = e[i].to;
if(v == fa) continue;
p[v] = pii(e[i].col,e[i].len); //边权下沉转换为点权
dp[v][0] = x; dfs(v,x,depth+1);
}
A[++tot] = x; ed[x] = tot;
}
void init(){
for(int i = 1;(1<<i)<=n; ++i)
for(int j = 1;j <= n; ++j)
dp[j][i] = dp[dp[j][i-1]][i-1];
}
int LCA(int u,int v){
if(deep[u] < deep[v]) swap(u,v);
int h = deep[u] - deep[v];
for(int i = 0;i < 20; ++i){
if(h&(1<<i)) u = dp[u][i];
}
if(u == v) return u;
for(int i = 19; ~i; --i){
if(dp[u][i] != dp[v][i]){
u = dp[u][i];
v = dp[v][i];
}
}
return dp[u][0];
}
int block,num[maxn],sum[maxn],vis[maxn],res;
bool cmp(query a,query b){
return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}
void add(int v){
if(vis[v]) {num[p[v].fi]--;sum[p[v].fi]-=p[v].se;res-=p[v].se;}
else {num[p[v].fi]++;sum[p[v].fi]+=p[v].se;res+=p[v].se;}
vis[v] ^= 1;
}
void del(int v){
if(vis[v]) {num[p[v].fi]--;sum[p[v].fi]-=p[v].se;res-=p[v].se;}
else {num[p[v].fi]++;sum[p[v].fi]+=p[v].se;res+=p[v].se;}
vis[v] ^= 1;
}
int main(){
scanf("%d %d",&n,&Q); block = sqrt(n*1.0);
for(int i = 1;i < n; ++i){
scanf("%d %d %d %d",&a,&b,&c,&d);
add(a,b,c,d); add(b,a,c,d);
}
dfs(1,0,1); init();
for(int i = 0;i < Q; ++i){
scanf("%d %d %d %d",&a,&b,&c,&d);
if(st[c] > st[d]) swap(c,d);
if(LCA(c,d) == c) q[i] = (query){st[c]+1,st[d],a,b,i}; //两种不同的情况转换为的区间也是不同的
else q[i] = (query){ed[c],st[d],a,b,i};
}
sort(q,q+Q,cmp);
int L = 1,R = 0; res = 0;
for(int i = 0;i < Q; ++i){
while(R > q[i].r) del(A[R]),--R;
while(R < q[i].r) ++R,add(A[R]);
while(L < q[i].l) del(A[L]),++L;
while(L > q[i].l) --L,add(A[L]);
ans[q[i].id] = res-sum[q[i].x]+num[q[i].x]*q[i].y;
}
for(int i = 0;i < Q; ++i) printf("%d\n",ans[i]);
return 0;
} （2）第二种方法当然就是树剖+主席树，由于修改的是颜色的信息，只需要知道这条路径上颜色为 x 的个数和边权和，还有路径的总长度，就可以快速得到答案；那么树剖后对颜色建主席树，每次在树链上跳的时候，查询相应的信息即可 ，和上面一样还是要边权转点权，这样查询的时候就有细节了
代码：
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
const int maxn = 2e5+15;
int n,Q,a,b,c,d,cnt,head[maxn];
struct edge{
int to,nxt,col,len;
}e[maxn<<1];
pii p[maxn];
inline void add(int u,int v,int c,int d){
e[++cnt] = (edge){v,head[u],c,d};
head[u] = cnt;
}
int fa[maxn],sz[maxn],son[maxn],dep[maxn];
void dfs1(int x,int pa,int depth){
dep[x] = depth; fa[x] = pa; sz[x] = 1;
for(int i = head[x];i > 0; i=e[i].nxt){
int v = e[i].to; if(v == pa) continue;
dfs1(v,x,depth+1); sz[x] += sz[v];
p[v] = pii(e[i].col,e[i].len); //边权转点权
if(sz[v] > sz[son[x]]) son[x] = v;
}
}
int id[maxn],top[maxn],rk[maxn],tot;
void dfs2(int x,int t){
top[x] = t; id[x] = ++tot; rk[tot] = x;
if(!son[x]) return ; dfs2(son[x],t);
for(int i = head[x];i > 0;i = e[i].nxt){
int v = e[i].to;
if(v==son[x]||v==fa[x]) continue;
dfs2(v,v);
}
}
struct tree{
int l,r,num,sum;
}T[maxn*160];
int root[maxn],k,x,y,u,v;
void build(int l,int r,int &x,int y,int c,int d){
T[++k] = T[y];T[k].num++;T[k].sum+=d;x = k;
if(l == r) return ;
int mid = (l+r) >> 1;
if(c > mid) build(mid+1,r,T[x].r,T[y].r,c,d);
else build(l,mid,T[x].l,T[y].l,c,d);
}
void query(int l,int r,int L,int R,int ql,int qr,int &num,int &sum){
if(l > R || r < L) return ;
if(l >= L && r <= R){
num += T[qr].num - T[ql].num;
sum += T[qr].sum - T[ql].sum;
return ;
}
int mid = (l+r) >> 1;
query(l,mid,L,R,T[ql].l,T[qr].l,num,sum);
query(mid+1,r,L,R,T[ql].r,T[qr].r,num,sum);
}
int solve(int u,int v,int x,int y){
int res = 0,num = 0,sum = 0;
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]]) swap(u,v);
query(0,n,x,x,root[id[top[u]]-1],root[id[u]],num,sum); //因为点top[u]保存的边的信息是要计算的,所以-1
res += T[root[id[u]]].sum - T[root[id[top[u]]-1]].sum; //总长度当然是所有颜色的和
u = fa[top[u]];
}
if(id[u] > id[v]) swap(u,v);
query(0,n,x,x,root[id[u]],root[id[v]],num,sum); //最后u,v在一条链上,点u保存的边不在u到v的路径上,所以就不-1
res += T[root[id[v]]].sum - T[root[id[u]]].sum;
return res - sum + num*y;
}
int main(){
scanf("%d %d",&n,&Q);
for(int i = 1;i < n; ++i){
scanf("%d %d %d %d",&a,&b,&c,&d);
add(a,b,c,d); add(b,a,c,d);
}
dfs1(1,0,1); dfs2(1,1);
for(int i = 1;i <= n; ++i) build(0,n,root[i],root[i-1],p[rk[i]].fi,p[rk[i]].se);
while(Q--){
scanf("%d %d %d %d",&x,&y,&u,&v);
printf("%d\n",solve(u,v,x,y));
}
return 0;
}
（3）第三种做法大致是将每次询问拆分成 u，v，lca 并在其节点上做好标记，然后一次 dfs 就解决了，相当于维护每个点到根的信息，用容斥的思想来计算每次询问的答案，网上代码多就不放了（实际上是没有写）