[POJ3237][树链剖分]Tree

2021-02-13编程中国发消息

Description

You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each edge is associated with a weight. Then you are to execute a series of instructions on the tree. The instructions can be one of the following forms:

`CHANGE` i v	Change the weight of the ith edge to v
`NEGATE` a b	Negate the weight of every edge on the path from a to b
`QUERY` a b	Find the maximum weight of edges on the path from a to b

Input

The input contains multiple test cases. The first line of input contains an integer t (t ≤ 20), the number of test cases. Then follow the test cases.

Each test case is preceded by an empty line. The first nonempty line of its contains N (N ≤ 10,000). The next N − 1 lines each contains three integers a, b and c, describing an edge connecting nodes a and b with weight c. The edges are numbered in the order they appear in the input. Below them are the instructions, each sticking to the specification above. A lines with the word DONE ends the test case.

Output

For each QUERY instruction, output the result on a separate line.

Sample Input

1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE

Sample Output

1
3

Source

POJ Monthly--2007.06.03, Lei, Tao [分析] 好久没写了。写一道练练手。

  1 /*
  2 宋代苏轼
  3 《南乡子·重九涵辉楼呈徐君猷》
  4 霜降水痕收。浅碧鳞鳞露远洲。酒力渐消风力软，飕飕。破帽多情却恋头。
  5 佳节若为酬。但把清尊断送秋。万事到头都是梦，休休。明日黄花蝶也愁。
  6 */
  7 #include iostream
  8 #include cstdio
  9 #include algorithm
 10 #include cstring
 11 #include vector
 12 #include utility
 13 #include iomanip
 14 #include string
 15 #include cmath
 16 #include queue
 17 #include assert.h
 18 #include map
 19 #include ctime
 20 #include cstdlib
 21 #include stack
 22 #define LOCAL
 23 const int INF = 0x3f3f3f3f;
 24 const int maxn=100000 + 10;
 25 const int maxnode = 100000;
 26 const int maxm=100000 * 2 + 10;
 27 using namespace std;
 28 struct Node{//权值线段树 
 29        int l, r;
 30        int Max, Min;
 31        bool neg;//取反标记 
 32 }tree[maxn * 4];
 33 struct Edge{
 34        int u, v, w;
 35 }edges[maxn];//输入的边 
 36 
 37 int n, fa[maxn], size[maxn];
 38 int son[maxn], dep[maxn], top[maxn];
 39 int pos[maxn], Time;
 40 int M, head[maxn], next[maxm], to[maxm], w[maxm];
 41 
 42 //第一次dfs 
 43 void dfs_1(int u){
 44      size[u] = 1;
 45      son[u] = 0;
 46      for (int i = head[u]; i != -1; i = next[i]){
 47          int v = to[i];
 48          if (v == fa[u]) continue;
 49          dep[v] = dep[u] + 1;
 50          fa[v] = u;
 51          dfs_1(v);
 52          size[u] += size[v];
 53          if (size[v]  size[son[u]]) son[u] = v;
 54      }
 55      return;
 56 }
 57 void dfs_2(int u, int top_node){
 58      top[u] = top_node;
 59      pos[u] = ++Time;//给他和他的父亲的边在线段树中的位置 
 60      //重边
 61      if (son[u]) dfs_2(son[u], top_node); 
 62      //轻边 
 63      for (int i = head[u]; i != -1; i = next[i]){
 64          int v = to[i];
 65          if (v == fa[u] || v == son[u]) continue;
 66          dfs_2(v, v);
 67      }
 68 }
 69 //建树 
 70 void build(int x, int l, int r){
 71      tree[x].l = l;tree[x].r = r;
 72      tree[x].Max = -INF;
 73      tree[x].Min = INF;
 74      tree[x].neg = 0;
 75      if (l == r) return;
 76      
 77      int mid = (l + r)  1;
 78      build(x  1, l, mid);
 79      build((x  1) | 1, mid + 1, r);
 80 }
 81 void update(int x){
 82      tree[x].Max = max(tree[x  1].Max, tree[(x  1) | 1].Max);
 83      tree[x].Min = min(tree[x  1].Min, tree[(x  1) | 1].Min);
 84      return;
 85 }
 86 //标记下传 
 87 void pushdown(int x){
 88      if (tree[x].l == tree[x].r) return;
 89      
 90      if (tree[x].neg){
 91         int l = (x  1), r = l | 1;
 92         tree[l].neg ^= 1;
 93         tree[l].Min *= -1;
 94         tree[l].Max *= -1;
 95         swap(tree[l].Min, tree[l].Max);
 96         
 97         tree[r].neg ^= 1;
 98         tree[r].Min *= -1;
 99         tree[r].Max *= -1;
100         swap(tree[r].Min, tree[r].Max);
101         
102         tree[x].neg = 0;
103      }
104 }
105 //在线段树中修改l,r为val 
106 void change2(int x, int l, int r, int val){
107      pushdown(x);
108      if (tree[x].l == l  tree[x].r == r){
109         if (val == INF){//取反操作,注意已经pushdown过了 
110            tree[x].neg = 1;
111            tree[x].Min *= -1;
112            tree[x].Max *= -1;
113            swap(tree[x].Min, tree[x].Max);
114         } else tree[x].Min = tree[x].Max = val;//更新val 
115         return;
116      }
117      
118      int mid = (tree[x].l + tree[x].r)  1;
119      if (r = mid) change2(x  1, l, r, val);
120      else if (l  mid) change2((x  1) | 1, l, r, val);
121      else{
122           change2(x  1, l, mid, val);
123           change2((x  1) | 1, mid + 1, r, val);
124      }
125      update(x);
126 }
127 int query2(int x, int l, int r){
128      pushdown(x);
129      if (tree[x].l == l  tree[x].r == r) return tree[x].Max;
130      
131      int mid = (tree[x].l + tree[x].r)  1; 
132      if (r = mid) return query2(x  1, l, r);
133      else if (l  mid) return query2((x  1) | 1, l, r);
134      else return max(query2((x  1), l, mid), query2((x  1) | 1, mid + 1, r));
135 }
136 //树链剖分部分 
137 void change(int x, int y, int v){
138      while (top[x] != top[y]){
139            //总是矮的往上爬.. 
140            //保证dep[top[x]] = dep[top[y]] 
141            if (dep[top[x]]  dep[top[y]]) swap(x, y);
142            
143            change2(1, pos[top[x]], pos[x], v);
144            x = fa[top[x]];
145      }
146      
147      if (x == y) return;
148      if (dep[x]  dep[y]) swap(x, y);
149      change2(1, pos[son[x]], pos[y], v);
150 }
151 int query(int x, int y){
152     int Ans = -INF;
153     while (top[x] != top[y]){
154           if (dep[top[x]]  dep[top[y]]) swap(x, y);
155           
156           Ans = max(Ans, query2(1, pos[top[x]], pos[x]));
157           x = fa[top[x]];
158     }
159     if (x == y) return Ans;
160     if (dep[x]  dep[y]) swap(x, y);
161     Ans = max(Ans, query2(1, pos[son[x]], pos[y]));
162     return Ans == -INF ? 0 : Ans;
163 }
164 void work(){
165     while(1){
166         char str[20];
167         scanf("%s", str);
168         if(str[0] == 'C'){
169             int x, v;
170             scanf("%d%d", x, v);
171             change2(1, pos[edges[x].v], pos[edges[x].v], v);
172         }else if(str[0] == 'N'){
173             int l, r;
174             scanf("%d%d", l, r);
175             change(l, r, INF);
176         }else if(str[0] == 'Q'){//询问两点之间最大值 
177             int l, r;
178             scanf("%d%d", l, r);
179             printf("%d\n", query(l, r));
180         }else break;
181     }
182 }
183 //加边 
184 void addEdge(int u, int v, int c){
185      to[M] = v;
186      w[M] = c;
187      next[M] = head[u];
188      head[u] = M++;
189 }
190 void init(){
191      memset(head, -1, sizeof(head));//邻接表初始化
192      memset(dep, 0, sizeof(dep));
193      M = Time = 0;//总边数和时间 
194      fa[1] = size[0] = 0;
195      //加边 
196      scanf("%d", n);
197      for (int i = 1; i  n; i++){
198          scanf("%d%d%d", edges[i].u, edges[i].v, edges[i].w);
199          addEdge(edges[i].u, edges[i].v, edges[i].w);
200          addEdge(edges[i].v, edges[i].u, edges[i].w);
201      }
202      dfs_1(1);
203      dfs_2(1, 1);
204      build(1, 1, Time);
205      for (int i = 1; i  n; i++){
206          int x = edges[i].u, y = edges[i].v;
207          //判断父亲 
208          if (dep[x]  dep[y]) swap(edges[i].u, edges[i].v);
209          //u一定是父亲 
210          change2(1, pos[edges[i].v], pos[edges[i].v], edges[i].w);
211     }
212 }
213 
214 int main(){
215     int T;
216     
217     scanf("%d", T);
218     while (T--){
219           init();
220           work();
221     }
222     //printf("%d\n", INF); 
223     return 0;
224 }