树链剖分模板题
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define N 50010 7 #define ls o<<1 8 #define rs o<<1|1 9 #define define_m int m=(l+r)>>1 10 #define ll long long 11 int first[N] , k; 12 struct Edge{ 13 int x , y , next , w; 14 }e[N<<1]; 15 16 void add_edge(int x , int y , int w) 17 { 18 e[k].x = x , e[k].y = y , e[k].next = first[x] , e[k].w = w; 19 first[x] = k++; 20 } 21 22 int sz[N] , dep[N] , fa[N] , son[N] , top[N] , id[N] , num; 23 void dfs(int u , int f , int d) 24 { 25 fa[u] = f , sz[u] = 1 , dep[u]= d , son[u]=0; 26 int mx = 0; 27 for(int i=first[u] ; ~i ; i=e[i].next){ 28 int v = e[i].y; 29 if(v == f) continue; 30 dfs(v , u , d+1); 31 sz[u]+=sz[v]; 32 if(sz[v]>mx) mx=sz[v] , son[u]=v; 33 } 34 } 35 36 void dfs1(int u , int f , int head) 37 { 38 top[u]=head , id[u]=++num; 39 if(son[u]) dfs1(son[u] , u , head); 40 for(int i=first[u] ; ~i ; i=e[i].next){ 41 int v = e[i].y; 42 if(v == f || v == son[u]) continue; 43 dfs1(v , u , v); 44 } 45 } 46 47 ll sum[N<<2] ; 48 int val[N]; 49 void push_up(int o) 50 { 51 sum[o] = sum[ls]+sum[rs]; 52 } 53 54 void build(int o , int l , int r) 55 { 56 if(l==r){ 57 sum[o]=(ll)val[l]; 58 return ; 59 } 60 define_m; 61 build(ls , l , m); 62 build(rs , m+1 , r); 63 push_up(o); 64 } 65 66 void update(int o , int l , int r , int p , int v) 67 { 68 if(l==r){ 69 sum[o]=(ll)v; 70 return; 71 } 72 define_m; 73 if(m>=p) update(ls , l , m , p , v); 74 else update(rs , m+1 , r , p , v); 75 push_up(o); 76 } 77 78 ll qSum(int o , int l , int r , int s , int t) 79 { 80 if(l>=s && r<=t) return sum[o]; 81 define_m; 82 ll res = 0; 83 if(m>=s) res+=qSum(ls , l , m , s , t); 84 if(m<t) res+=qSum(rs , m+1 , r , s , t); 85 return res; 86 } 87 88 ll calPath(int u , int v) 89 { 90 int top1 = top[u] , top2 = top[v] ; 91 ll ret=0; 92 while(top1!=top2){ 93 if(dep[top1]<dep[top2]){ 94 swap(top1 , top2); 95 swap(u , v); 96 } 97 ret+=qSum(1 , 1 , num , id[top1] , id[u]); 98 u = fa[top1]; 99 top1 = top[u]; 100 } 101 if(u!=v){ 102 if(dep[u]<dep[v]) swap(u,v); 103 ret+=qSum(1,1,num,id[son[v]],id[u]); 104 } 105 return ret; 106 } 107 108 int main() 109 { 110 // freopen("in.txt" , "r" , stdin); 111 int n , m , x , y , w; 112 while(scanf("%d%d" , &n , &m)!=EOF) 113 { 114 memset(first , -1 , sizeof(first)); 115 k = 0; 116 for(int i=0 ; i<n-1 ; i++){ 117 scanf("%d%d%d" , &x , &y , &w); 118 add_edge(x , y , w); 119 add_edge(y , x , w); 120 } 121 dfs(1 , 0 , 1); 122 num = 0; 123 dfs1(1 , 0 , 1); 124 for(int i=0 ; i<n-1 ; i++){ 125 x = e[i*2].x , y = e[i*2].y; 126 if(fa[x]!=y) val[id[y]] = e[i*2].w; 127 else val[id[x]] = e[i*2].w; 128 } 129 build(1 , 1 , num); 130 while(m--){ 131 scanf("%d%d%d" , &w , &x , &y); 132 if(w){ 133 printf("%I64d " , calPath(x , y)); 134 }else{ 135 x--; 136 int pos; 137 if(fa[e[x*2].x]!=e[x*2].y) pos = id[e[x*2].y]; 138 else pos = id[e[x*2].x]; 139 update(1 , 1 , num , pos , y); 140 } 141 } 142 } 143 return 0; 144 }