POJ 2763 Housewife Wind (树链剖分有修改单边权)

n个节点的树上知道了每条边权，然后有两种操作：0操作是输出当前节点到 x节点的最短距离，并移动到 x 节点位置；1操作是第i条边的边权变成x。
树链边权剖分的模版题，修改单边权和求和。
  1 //#pragma comment(linker, "/STACK:102400000,102400000")
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstring>
  5 using namespace std;
  6 const int MAXN = 1e5 + 5;
  7 struct EDGE {
  8     int next, to, cost;
  9 }edge[MAXN << 2];
 10 int head[MAXN], tot;
 11 int from[MAXN], to[MAXN], cost[MAXN];
 12 int par[MAXN], dep[MAXN], son[MAXN], size[MAXN];
 13 int top[MAXN], id[MAXN], cnt;
 14 
 15 void init() {
 16     cnt = tot = 0;
 17     memset(head, -1, sizeof(head));
 18 }
 19 
 20 inline void add(int u, int v, int cost) {
 21     edge[tot].next = head[u];
 22     edge[tot].to = v;
 23     head[u] = tot++;
 24 }
 25 
 26 void dfs1(int u, int p, int d) {
 27     dep[u] = d, par[u] = p, size[u] = 1, son[u] = u;
 28     for(int i = head[u]; ~i; i = edge[i].next) {
 29         int v = edge[i].to;
 30         if(v == p)
 31             continue;
 32         dfs1(v, u, d + 1);
 33         if(size[v] >= size[son[u]])
 34             son[u] = v;
 35         size[u] += size[v];
 36     }
 37 }
 38 
 39 void dfs2(int u, int p, int t) {
 40     top[u] = t, id[u] = ++cnt;
 41     if(son[u] != u)
 42         dfs2(son[u], u, t);
 43     for(int i = head[u]; ~i; i = edge[i].next) {
 44         int v = edge[i].to;
 45         if(v == son[u] || v == p)
 46             continue;
 47         dfs2(v, u, v);
 48     }
 49 }
 50 
 51 struct segtree {
 52     int l, r, val;
 53 }T[MAXN << 2];
 54 
 55 void build(int p, int l, int r) {
 56     int mid = (l + r) >> 1;
 57     T[p].l = l , T[p].r = r;
 58     if(l == r) {
 59         return ;
 60     }
 61     build(p << 1, l, mid);
 62     build((p << 1)|1, mid + 1, r);
 63 }
 64 
 65 void updata(int p, int pos, int num) {
 66     int mid = (T[p].l + T[p].r) >> 1;
 67     if(T[p].l == T[p].r && T[p].l == pos) {
 68         T[p].val = num;
 69         return ;
 70     }
 71     if(pos <= mid) {
 72         updata(p << 1, pos, num);
 73     }
 74     else {
 75         updata((p << 1)|1, pos, num);
 76     }
 77     T[p].val = T[p << 1].val + T[(p << 1)|1].val;
 78 }
 79 
 80 int query(int p, int l, int r) {
 81     int mid = (T[p].l + T[p].r) >> 1;
 82     if(l == T[p].l && T[p].r == r) {
 83         return T[p].val;
 84     }
 85     if(r <= mid) {
 86         return query(p << 1, l, r);
 87     }
 88     else if(l > mid) {
 89         return query((p << 1)|1, l, r);
 90     }
 91     else {
 92         return query(p << 1, l, mid) + query((p << 1)|1, mid + 1, r);
 93     }
 94 }
 95 
 96 int find(int u, int v) {
 97     int fu = top[u], fv = top[v], res = 0;
 98     while(fv != fu) {
 99         if(dep[fu] > dep[fv]) {
100             res += query(1, id[fu], id[u]);
101             u = par[fu];
102             fu = top[u];
103         }
104         else {
105             res += query(1, id[fv], id[v]);
106             v = par[fv];
107             fv = top[v];
108         }
109     }
110     if(v == u)
111         return res;
112     else if(dep[u] > dep[v])
113         return res + query(1, id[son[v]], id[u]);
114     else
115         return res + query(1, id[son[u]], id[v]);
116 }
117 
118 int main()
119 {
120     int n, m, root;
121     while(~scanf("%d %d %d", &n, &m, &root)) {
122         init();
123         for(int i = 1; i < n; ++i) {
124             scanf("%d %d %d", from + i, to + i, cost + i);
125             add(from[i], to[i], cost[i]);
126             add(to[i], from[i], cost[i]);
127         }
128         dfs1(1, 1, 0);
129         dfs2(1, 1, 1);
130         build(1, 1, cnt);
131         for(int i = 1; i < n; ++i) {
132             if(dep[from[i]] < dep[to[i]])
133                 swap(from[i], to[i]);
134             updata(1, id[from[i]], cost[i]);
135         }
136         int op, pos, num;
137         while(m--) {
138             scanf("%d", &op);
139             if(op) {
140                 scanf("%d %d", &pos, &num);
141                 updata(1, id[from[pos]], num);
142             }
143             else {
144                 scanf("%d", &pos);
145                 printf("%d
", find(root, pos));
146                 root = pos;
147             }
148         }
149     }
150 }
POJ 2763 Housewife Wind (树链剖分 有修改单边权)

POJ 2763 Housewife Wind (树链剖分有修改单边权)
