[spoj 375]QTREE - Query on a tree[树链剖分]

  1 #include <cstdio>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <string.h>
  5 using namespace std;
  6 const int maxn = 10010;
  7 struct Tedge
  8 { int b, next; } e[maxn * 2];
  9 int tree[maxn];
 10 int zzz, n, z, edge, root, a, b, c;
 11 int d[maxn][3];
 12 int first[maxn], dep[maxn], w[maxn], fa[maxn], top[maxn], son[maxn], siz[maxn];
 13 char ch[10];
 14 
 15 void insert(int a, int b, int c){
 16     e[++edge].b = b;
 17     e[edge].next = first[a];
 18     first[a] = edge;
 19 }
 20 
 21 void dfs(int v){
 22     siz[v] = 1; son[v] = 0;
 23     for (int i = first[v]; i > 0; i = e[i].next)
 24         if (e[i].b != fa[v]){
 25             fa[e[i].b] = v;
 26             dep[e[i].b] = dep[v]+1;
 27             dfs(e[i].b);
 28             if (siz[e[i].b] > siz[son[v]]) son[v] = e[i].b;
 29             siz[v] += siz[e[i].b];
 30         }
 31 }
 32 
 33 void build_tree(int v, int tp){
 34     w[v] = ++ z; top[v] = tp;
 35     if (son[v] != 0) build_tree(son[v], top[v]);
 36     for (int i = first[v]; i > 0; i = e[i].next)
 37         if (e[i].b != son[v] && e[i].b != fa[v])
 38             build_tree(e[i].b, e[i].b);
 39 }
 40 
 41 void update(int root, int lo, int hi, int loc, int x){
 42     if (loc > hi || lo > loc) return;
 43     if (lo == hi)
 44     { tree[root] = x; return; }
 45     int mid = (lo + hi) / 2, ls = root * 2, rs = ls + 1;
 46     update(ls, lo, mid, loc, x);
 47     update(rs, mid+1, hi, loc, x);
 48     tree[root] = max(tree[ls], tree[rs]);
 49 }
 50 
 51 int maxi(int root, int lo, int hi, int l, int r){
 52     if (l > hi || r < lo) return 0;
 53     if (l <= lo && hi <= r) return tree[root];
 54     int mid = (lo + hi) / 2, ls = root * 2, rs = ls + 1;
 55     return max(maxi(ls, lo, mid, l, r), maxi(rs, mid+1, hi, l, r));
 56 }
 57 
 58 inline int find(int va, int vb){
 59     int f1 = top[va], f2 = top[vb], tmp = 0;
 60     while (f1 != f2){
 61         if (dep[f1] < dep[f2])
 62         { swap(f1, f2); swap(va, vb); }
 63         tmp = max(tmp, maxi(1, 1, z, w[f1], w[va]));
 64         va = fa[f1]; f1 = top[va];
 65     }
 66     if (va == vb) return tmp;
 67     if (dep[va] > dep[vb]) swap(va, vb);
 68     return max(tmp, maxi(1, 1, z, w[son[va]], w[vb]));  //
 69 }
 70 
 71 void init(){
 72     scanf("%d", &n);
 73     root = (n + 1) / 2;
 74     fa[root] = z = dep[root] = edge = 0;
 75     memset(siz, 0, sizeof(siz));
 76     memset(first, 0, sizeof(first));
 77     memset(tree, 0, sizeof(tree));
 78     for (int i = 1; i < n; i++){
 79         scanf("%d%d%d", &a, &b, &c);
 80         d[i][0] = a; d[i][1] = b; d[i][2] = c;
 81         insert(a, b, c);
 82         insert(b, a, c);
 83     }
 84     dfs(root);
 85     build_tree(root, root);    //
 86     for (int i = 1; i < n; i++){
 87         if (dep[d[i][0]] > dep[d[i][1]]) swap(d[i][0], d[i][1]);
 88         update(1, 1, z, w[d[i][1]], d[i][2]);
 89     }
 90 }
 91 
 92 inline void read(){
 93     ch[0] = ‘ ‘;
 94     while (ch[0] < ‘C‘ || ch[0] > ‘Q‘) scanf("%s", &ch);
 95 }
 96 
 97 void work()
 98 {
 99     for (read(); ch[0] != ‘D‘; read()){
100         scanf("%d%d", &a, &b);
101         if (ch[0] == ‘Q‘) printf("%d\n", find(a, b));
102         else update(1, 1, z, w[d[a][1]], b);
103     }
104 }
105 
106 int main(){
107     for (scanf("%d", &zzz); zzz > 0; zzz--){
108         init();
109         work();
110     }
111     return 0;
112 }