原理简介
众所周知，树链剖分模板是用来维护点上信息的，但是也可通过对边的转化维护边的信息。
由于只有n-1条边，一般选择将所有边挂在dep[]更深的点上结果使根节点上无值，然后修改原来处理链的函数，核心代码：
if(x ^ y) {
if(dep[x] > dep[y]) swap(x,y);
ans += qsum(1,1,n,seg[son[x]],seg[y]);
}
？？？为什么y一定在x的重儿子为根的子树上呢？我们考虑之前的while循环，设dep[top[x]] > dep[top[y]],所以每次都是把x - top[x]的支链求出答案，由假设得top[x]一定在以top[y]为根的子树内，但是top[x]管辖的链开头是自己，所以他并不是top[y]为根的子树内的重链。跳出循环时两点一定top[y]为根的子树的重链上。
例题
Housewife Wind
模板题
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <algorithm>
#define ll long long
#define rint register int
#define mid ((L + R) >> 1)
#define lson (x << 1)
#define rson (x << 1 | 1)
using namespace std;
template<typename xxx>inline void read(xxx &x) {
int f = 1;char c = getchar();x = 0;
for(;c ^ '-' && !isdigit(c);c = getchar());
if(c == '-') f = -1,c = getchar();
for(;isdigit(c);c = getchar()) x = (x<<3) + (x<<1) + (c ^ '0');
x *= f;
}
template<typename xxx>inline void print(xxx x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) print(x / 10);
putchar(x % 10 + '0');
}
const int maxn = 100010;
const int mod = 998244353;
const int inf = 0x7fffffff;
struct node{
int a,b,id;ll c;
}g[maxn];
struct edge {
int to,last;
ll val;
}e[maxn<<1];
int head[maxn],tot;
inline void add(int from,int to,ll val) {
++tot;
e[tot].to = to;
e[tot].val = val;
e[tot].last = head[from];
head[from] = tot;
}
int n,m,s;
int w[maxn],cnt;
int dad[maxn];
int dep[maxn];
int rev[maxn];
int seg[maxn];
int siz[maxn];
int son[maxn];
int top[maxn];
inline void ddfs1(int x,int da) {
son[x] = 0;
siz[x] = 1;dad[x] = da;
dep[x] = dep[da] + 1;
for(rint i = head[x];i;i = e[i].last) {
if(e[i].to == da) continue;
ddfs1(e[i].to,x);
w[e[i].to] = g[e[i].val].c;
g[e[i].val].id = e[i].to;
siz[x] += siz[e[i].to];
if(son[x] == 0 || siz[son[x]] < siz[e[i].to]) son[x] = e[i].to;
}
return ;
}
inline void ddfs2(int x,int tp) {
seg[x] = ++cnt;
rev[cnt] = x;
top[x] = tp;
if(!son[x]) return ;
ddfs2(son[x],tp);
for(rint i = head[x];i;i = e[i].last) {
if(e[i].to == dad[x] || e[i].to == son[x]) continue;
ddfs2(e[i].to,e[i].to);
}
return ;
}
ll sum[maxn<<2];
inline void pushup(int x) {
sum[x] = sum[lson] + sum[rson];
}
inline void build(int x,int L,int R) {
sum[x] = 0;
if(L == R) {
sum[x] = w[rev[L]];
return ;
}
build(lson,L,mid);
build(rson,mid + 1,R);
pushup(x);
}
inline void update(int x,int L,int R,int pos,ll val) {
if(L == R) {
sum[x] = val;
return;
}
if(pos <= mid) update(lson,L,mid,pos,val);
else update(rson,mid + 1,R,pos,val);
pushup(x);
return ;
}
inline ll qsum(int x,int L,int R,int l,int r) {
if(l <= L && R <= r) return sum[x];
ll ans = 0;
if(l <= mid) ans += qsum(lson,L,mid,l,r);
if(r > mid) ans += qsum(rson,mid + 1,R,l,r);
return ans;
}
inline ll q1(int x,int y) {
ll ans = 0;
while(top[x] ^ top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x,y);
ans += qsum(1,1,n,seg[top[x]],seg[x]);
x = dad[top[x]];
}
if(x ^ y) {
if(dep[x] > dep[y]) swap(x,y);
ans += qsum(1,1,n,seg[son[x]],seg[y]);
}
return ans;
}
int main() {
while(~scanf("%d%d%d",&n,&m,&s)) {//小心可恶的多重数据
for(rint i = 1;i < n; ++i) {
read(g[i].a);read(g[i].b);read(g[i].c);
add(g[i].a,g[i].b,i);
add(g[i].b,g[i].a,i);
}
ddfs1(1,0);
ddfs2(1,1);
build(1,1,n);
for(rint i = 1;i <= m; ++i) {
ll opt,a,b;
read(opt);
if(opt) {
read(a);read(b);
update(1,1,n,seg[g[a].id],b);
} else {
read(a);
print(q1(a,s));
putchar('
');
s = a;
}
}
tot = 0;cnt = 0;
memset(head,0,sizeof(head));
}
return 0;
}
/*
*/