【POJ3237】【树链剖分】Tree

 /*

 宋代苏轼

 《南乡子·重九涵辉楼呈徐君猷》

 霜降水痕收。浅碧鳞鳞露远洲。酒力渐消风力软，飕飕。破帽多情却恋头。

 佳节若为酬。但把清尊断送秋。万事到头都是梦，休休。明日黄花蝶也愁。

 */

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 #include <vector>

 #include <utility>

 #include <iomanip>

 #include <string>

 #include <cmath>

 #include <queue>

 #include <assert.h>

 #include <map>

 #include <ctime>

 #include <cstdlib>

 #include <stack>

 #define LOCAL

 const int INF = 0x3f3f3f3f;

 const int maxn= + ;

 const int maxnode = ;

 const int maxm= *  + ;

 using namespace std;

 struct Node{//权值线段树

        int l, r;

        int Max, Min;

        bool neg;//取反标记

 }tree[maxn * ];

 struct Edge{

        int u, v, w;

 }edges[maxn];//输入的边 

 int n, fa[maxn], size[maxn];

 int son[maxn], dep[maxn], top[maxn];

 int pos[maxn], Time;

 int M, head[maxn], next[maxm], to[maxm], w[maxm];

 //第一次dfs

 void dfs_1(int u){

      size[u] = ;

      son[u] = ;

      for (int i = head[u]; i != -; i = next[i]){

          int v = to[i];

          if (v == fa[u]) continue;

          dep[v] = dep[u] + ;

          fa[v] = u;

          dfs_1(v);

          size[u] += size[v];

          if (size[v] > size[son[u]]) son[u] = v;

      }

      return;

 }

 void dfs_2(int u, int top_node){

      top[u] = top_node;

      pos[u] = ++Time;//给他和他的父亲的边在线段树中的位置

      //重边

      if (son[u]) dfs_2(son[u], top_node);

      //轻边

      for (int i = head[u]; i != -; i = next[i]){

          int v = to[i];

          if (v == fa[u] || v == son[u]) continue;

          dfs_2(v, v);

      }

 }

 //建树

 void build(int x, int l, int r){

      tree[x].l = l;tree[x].r = r;

      tree[x].Max = -INF;

      tree[x].Min = INF;

      tree[x].neg = ;

      if (l == r) return;

      int mid = (l + r) >> ;

      build(x << , l, mid);

      build((x << ) | , mid + , r);

 }

 void update(int x){

      tree[x].Max = max(tree[x << ].Max, tree[(x << ) | ].Max);

      tree[x].Min = min(tree[x << ].Min, tree[(x << ) | ].Min);

      return;

 }

 //标记下传

 void pushdown(int x){

      if (tree[x].l == tree[x].r) return;

      if (tree[x].neg){

         int l = (x << ), r = l | ;

         tree[l].neg ^= ;

         tree[l].Min *= -;

         tree[l].Max *= -;

         swap(tree[l].Min, tree[l].Max);

         tree[r].neg ^= ;

         tree[r].Min *= -;

         tree[r].Max *= -;

         swap(tree[r].Min, tree[r].Max);

         tree[x].neg = ;

      }

 }

 //在线段树中修改l,r为val

 void change2(int x, int l, int r, int val){

      pushdown(x);

      if (tree[x].l == l && tree[x].r == r){

         if (val == INF){//取反操作,注意已经pushdown过了

            tree[x].neg = ;

            tree[x].Min *= -;

            tree[x].Max *= -;

            swap(tree[x].Min, tree[x].Max);

         } else tree[x].Min = tree[x].Max = val;//更新val

         return;

      }

      int mid = (tree[x].l + tree[x].r) >> ;

      if (r <= mid) change2(x << , l, r, val);

      else if (l > mid) change2((x << ) | , l, r, val);

      else{

           change2(x << , l, mid, val);

           change2((x << ) | , mid + , r, val);

      }

      update(x);

 }

 int query2(int x, int l, int r){

      pushdown(x);

      if (tree[x].l == l && tree[x].r == r) return tree[x].Max;

      int mid = (tree[x].l + tree[x].r) >> ;

      if (r <= mid) return query2(x << , l, r);

      else if (l > mid) return query2((x << ) | , l, r);

      else return max(query2((x << ), l, mid), query2((x << ) | , mid + , r));

 }

 //树链剖分部分

 void change(int x, int y, int v){

      while (top[x] != top[y]){

            //总是矮的往上爬..

            //保证dep[top[x]] >= dep[top[y]]

            if (dep[top[x]] < dep[top[y]]) swap(x, y);

            change2(, pos[top[x]], pos[x], v);

            x = fa[top[x]];

      }

      if (x == y) return;

      if (dep[x] > dep[y]) swap(x, y);

      change2(, pos[son[x]], pos[y], v);

 }

 int query(int x, int y){

     int Ans = -INF;

     while (top[x] != top[y]){

           if (dep[top[x]] < dep[top[y]]) swap(x, y);

           Ans = max(Ans, query2(, pos[top[x]], pos[x]));

           x = fa[top[x]];

     }

     if (x == y) return Ans;

     if (dep[x] > dep[y]) swap(x, y);

     Ans = max(Ans, query2(, pos[son[x]], pos[y]));

     return Ans == -INF ?  : Ans;

 }

 void work(){

     while(){

         char str[];

         scanf("%s", str);

         if(str[] == 'C'){

             int x, v;

             scanf("%d%d", &x, &v);

             change2(, pos[edges[x].v], pos[edges[x].v], v);

         }else if(str[] == 'N'){

             int l, r;

             scanf("%d%d", &l, &r);

             change(l, r, INF);

         }else if(str[] == 'Q'){//询问两点之间最大值

             int l, r;

             scanf("%d%d", &l, &r);

             printf("%d\n", query(l, r));

         }else break;

     }

 }

 //加边

 void addEdge(int u, int v, int c){

      to[M] = v;

      w[M] = c;

      next[M] = head[u];

      head[u] = M++;

 }

 void init(){

      memset(head, -, sizeof(head));//邻接表初始化

      memset(dep, , sizeof(dep));

      M = Time = ;//总边数和时间

      fa[] = size[] = ;

      //加边

      scanf("%d", &n);

      for (int i = ; i < n; i++){

          scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);

          addEdge(edges[i].u, edges[i].v, edges[i].w);

          addEdge(edges[i].v, edges[i].u, edges[i].w);

      }

      dfs_1();

      dfs_2(, );

      build(, , Time);

      for (int i = ; i < n; i++){

          int x = edges[i].u, y = edges[i].v;

          //判断父亲

          if (dep[x] > dep[y]) swap(edges[i].u, edges[i].v);

          //u一定是父亲

          change2(, pos[edges[i].v], pos[edges[i].v], edges[i].w);

     }

 }

 int main(){

     int T;

     scanf("%d", &T);

     while (T--){

           init();

           work();

     }

     //printf("%d\n", INF);

     return ;

 }