題目：
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 就解決了，相當于維護每個點到根的資訊，用容斥的思想來計算每次詢問的答案，網上代碼多就不放了（實際上是沒有寫）