题目链接：?id=2763
题意：给一个数，，边之间有权值，然后两种操作，第一种：求任意两点的权值和，第二，修改树上两点的权值。
题解：简单的树链剖分。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int M = 1e5 + 10; struct Edge { int v , next; }edge[M << 1]; int head[M] , e; int top[M]; int fa[M]; int num[M]; int p[M]; int fp[M]; int deep[M]; int son[M]; int pos; void init() { memset(head , -1 , sizeof(head)); memset(son , -1 , sizeof(son)); e = 0; pos = 1; } void add(int u , int v) { edge[e].v = v; edge[e].next = head[u]; head[u] = e++; } void dfs1(int u , int pre , int d) { deep[u] = d; fa[u] = pre; num[u] = 1; for(int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].v; if(v != pre) { dfs1(v , u , d + 1); num[u] += num[v]; if(son[u] == -1 || num[son[u]] < num[v]) { son[u] = v; } } } } void getpos(int u , int sp) { top[u] = sp; p[u] = pos++; fp[p[u]] = u; if(son[u] == -1) return ; getpos(son[u] , sp); for(int i = head[u] ; i != -1 ; i = edge[i].next) { int v = edge[i].v; if(v != son[u] && v != fa[u]) { getpos(v , v); } } } struct TnT { int l , r , sum; }T[M << 2]; int ed[M][3]; void pushup(int i) { T[i].sum = T[i << 1].sum + T[(i << 1) | 1].sum; } void build(int l , int r , int i) { int mid = (l + r) >> 1; T[i].l = l , T[i].r = r , T[i].sum = 0; if(l == r) { return ; } build(l , mid , i << 1); build(mid + 1 , r , (i << 1) | 1); pushup(i); } void updata(int pos , int i , int ad) { int mid = (T[i].l + T[i].r) >> 1; if(T[i].l == T[i].r && T[i].l == pos) { T[i].sum = ad; return ; } if(mid < pos) { updata(pos , (i << 1) | 1 , ad); } else { updata(pos , i << 1 , ad); } pushup(i); } int query(int l , int r , int i) { int mid = (T[i].l + T[i].r) >> 1; if(T[i].l == l && T[i].r == r) { return T[i].sum; } pushup(i); if(mid < l) { return query(l , r , (i << 1) | 1); } else if(mid >= r) { return query(l , r , i << 1); } else { return query(l , mid , i << 1) + query(mid + 1 , r , (i << 1) | 1); } } int find(int u , int v) { int f1 = top[u] , f2 = top[v]; int tmp = 0; while(f1 != f2) { if(deep[f1] < deep[f2]) { swap(f1 , f2); swap(u , v); } tmp += query(p[f1] , p[u] , 1); u = fa[f1] , f1 = top[u]; } if(u == v) return tmp; if(deep[u] > deep[v]) swap(u , v); return tmp + query(p[son[u]] , p[v] , 1); } int main() { int n , q , s , cp , u , v; scanf("%d%d%d" , &n , &q , &s); init(); for(int i = 0 ; i < n - 1 ; i++) { for(int j = 0 ; j < 3 ; j++) { scanf("%d" , &ed[i][j]); } add(ed[i][0] , ed[i][1]); add(ed[i][1] , ed[i][0]); } dfs1(1 , 0 , 0); getpos(1 , 1); build(0 , pos , 1); for(int i = 0 ; i < n - 1 ; i++) { if(deep[ed[i][0]] > deep[ed[i][1]]) { swap(ed[i][0] , ed[i][1]); } updata(p[ed[i][1]] , 1 , ed[i][2]); } while(q--) { scanf("%d" , &cp); if(cp == 0) { scanf("%d" , &u); printf("%d\n" , find(s , u)); s = u; } else { scanf("%d%d" , &u , &v); updata(p[ed[u - 1][1]] , 1 , v); } } return 0; }poj 2763 Housewife Wind（树链剖分+单点查询+区间修改）