【题意说明】
给一个树，边之间有权值，然后两种操作，第一种：求任意两点的权值和，第二，修改树上某点的权值
本题就是对树进行单点更新和区域查询，显然可以使用树链剖分来完成。应该是一个比较基础的树链剖分题，注意每当区域查询后，要修改当前所有在的位置。
【参考代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define fr(i) edge[i].from
#define to(i) edge[i].to
#define nt(i) edge[i].next
#define vl(i) edge[i].value
#define hd(i) node[i].head
#define fa(i) node[i].father
#define dp(i) node[i].deep
#define sz(i) node[i].size
#define sn(i) node[i].son
#define cd(i) node[i].code
#define tp(i) node[i].top
#define lt(i) tree[i].left
#define rt(i) tree[i].right
#define vt(i) tree[i].value
#define lson k<<1
#define rson k<<1|1
const int maxN=100010;
struct Tree{
int left, right, value;
}tree[maxN<<2];
struct Edge{
int from, to, next, value;
}edge[maxN<<1];
struct Node{
int head, father, deep, size, son, code, top;
}node[maxN];
int n, q, s, total=0, cnt=0;
void addedge(int, int, int);
void build(int, int, int);
void update(int, int, int);
int query(int, int, int);
int solve(int, int);
void work();
void dfs1(int, int);
void dfs2(int, int);
int main(){
work();
return 0;
}
void work(){
memset(node, 0, sizeof(node));
memset(edge, 0, sizeof(edge));
memset(tree, 0, sizeof(tree));
scanf("%d%d%d", &n, &q, &s);
for(int i=0; i<n-1; i++){
int x, y, w;
scanf("%d%d%d", &x, &y, &w);
addedge(x, y, w);
addedge(y, x, w);
}
dfs1(1, 1);
dfs2(1, 1);
build(1, 1, total);
for(int i=1; i<cnt; i+=2){
int u=fr(i), v=to(i);
if(dp(u)<dp(v)) swap(u, v);
update(1, cd(u), vl(i));
}
for(int i=0; i<q; i++){
int t, u, v, x;
scanf("%d%d", &t, &u);
if(t){
scanf("%d", &x);
v=to(u-1<<1|1); u=fr(u-1<<1|1);
if(dp(u)<dp(v)) swap(u, v);
update(1, cd(u), x);
}else{
printf("%d ", solve(s, u));
s=u;
}
}
}
void addedge(int x, int y, int w){
fr(++cnt)=x; to(cnt)=y; vl(cnt)=w;
nt(cnt)=hd(x); hd(x)=cnt;
}
void dfs1(int u, int k){
sz(u)=1; dp(u)=k;
for(int i=hd(u); i; i=nt(i)){
if(sz(to(i))) continue;
fa(to(i))=u;
dfs1(to(i), k+1);
sz(u)+=sz(to(i));
if(sz(sn(u))<sz(to(i))) sn(u)=to(i);
}
}
void dfs2(int u, int _tp){
cd(u)=++total; tp(u)=_tp;
if(sn(u)) dfs2(sn(u), _tp);
for(int i=hd(u); i; i=nt(i))
if(!cd(to(i))) dfs2(to(i), to(i));
}
void build(int k, int l, int r){
lt(k)=l; rt(k)=r;
if(l==r) return;
int mid=(l+r)>>1;
build(lson, l, mid);
if(mid<r) build(rson, mid+1, r);
}
void update(int k, int x, int v){
if(lt(k)==rt(k)){
vt(k)=v;
return;
}
if(x<=rt(lson)) update(lson, x, v);
if(x>=lt(rson)) update(rson, x, v);
vt(k)=vt(lson)+vt(rson);
}
int solve(int u, int v){
int f1=tp(u), f2=tp(v), ans=0;
while(f1!=f2){
if(dp(f1)<dp(f2)){
swap(u, v);
swap(f1, f2);
}
ans+=query(1, cd(f1), cd(u));
u=fa(f1); f1=tp(u);
}
if(u==v) return ans;
if(dp(u)<dp(v)) swap(u, v);
return ans+=query(1, cd(sn(v)), cd(u));
}
int query(int k, int l, int r){
if(l<=lt(k)&&r>=rt(k)) return vt(k);
if(r<=rt(lson)) return query(lson, l, r);
if(l>=lt(rson)) return query(rson, l, r);
return query(lson, l, rt(lson))+query(rson, lt(rson), r);
}