【BZOJ1036】【树链剖分】树的统计Count

2022-11-04 09:07:09

Description

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. QSUM u v: 询问从点u到点v的路径上的节点的权值和注意：从点u到点v的路径上的节点包括u和v本身

Input

输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数 q，表示操作的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到 30000之间。

Output

对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

HINT

Source

树的分治

【分析】

SB题，不说了。

 /*

 唐代李白

 《南陵别儿童入京》

 白酒新熟山中归，黄鸡啄黍秋正肥。

 呼童烹鸡酌白酒，儿女嬉笑牵人衣。

 高歌取醉欲自慰，起舞落日争光辉。

 游说万乘苦不早，著鞭跨马涉远道。

 会稽愚妇轻买臣，余亦辞家西入秦。

 仰天大笑出门去，我辈岂是蓬蒿人。

 */

 #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, sum;

        Node *ch[];

 }*root, mem[maxnode];

 struct Edge{

        int u, v;

 }edge[MAXN];

 int n, top[MAXN], fa[MAXN];

 int dep[MAXN], size[MAXN], son[MAXN];

 int head[MAXN], next[MAXN], to[MAXN];

 int pos[MAXN], Time, M, tot;

 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;

          fa[v] = u;

          dep[v] = dep[u] + ;

          dfs_1(v);

          size[u] += size[v];

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

      }

 }

 //标号

 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 addEdge(int u, int v){

      to[M] = v;

      next[M] = head[u];

      head[u] = M++;

 }

 Node *NEW(int l, int r){

      Node *p = &mem[tot++];

      p->l = l;

      p->r = r;

      p->Max = p->sum = ;

      return p;

 }

 //连区间修改都没有

 void update(Node *&t){

      if (t->l == t->r) return;

      t->Max = max(t->ch[]->Max, t->ch[]->Max);

      t->sum = t->ch[]->sum + t->ch[]->sum;

 }

 void build(Node *&t, int l, int r){

      if (t == NULL){

         t = NEW(l, r);

      }

      if (l == r) return;

      int mid = (l + r) >> ;

      build(t->ch[], l, mid);

      build(t->ch[], mid + , r);

 }

 void change(Node *&t, int l, int x){

      if (t->l == l && t->r == l){

         t->sum = t->Max = x;

         return;

      }

      int mid = (t->l + t->r) >> ;

      if (l <= mid) change(t->ch[], l, x);

      else change(t->ch[], l, x);

      update(t);

 }

 void init(){

      memset(dep, , sizeof(dep));

      memset(head, -, sizeof(head));

      M = Time = tot = ;

      scanf("%d", &n);

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

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

          addEdge(edge[i].u, edge[i].v);

          addEdge(edge[i].v, edge[i].u);

      }

      fa[] = ;

      size[] = ;

      dfs_1();

      dfs_2(, );

      root = NULL;

      build(root, , Time);

      //因为不是边所以跟父亲没什么关系，不用对边进行更新

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

          int t;

          scanf("%d", &t);

          change(root, pos[i], t);

      }

      //printf("%d\n", root->Max);

 }

 int query_sum(Node *&t, int l, int r){

     if (l <= t->l && t->r <= r) return t->sum;

     int mid = (t->l + t->r) >> ;

     int cnt = ;

     if (l <= mid) cnt += query_sum(t->ch[], l, r);

     if (r > mid) cnt += query_sum(t->ch[], l, r);

     return cnt;

 }

 int query_max(Node *&t, int l, int r){

     if (l <= t->l && t->r <= r) return t->Max;

     int mid = (t->l + t->r) >> ;

     int Ans = -INF;

     if (l <= mid) Ans = max(Ans, query_max(t->ch[], l, r));

     if (r > mid) Ans = max(Ans, query_max(t->ch[], l, r));

     return Ans;

 }

 int QMAX(int l, int r){

      int Ans = -INF;

      while (top[l] != top[r]){

            //低的往上爬

            if (dep[top[l]] < dep[top[r]]) swap(l, r);

            Ans = max(Ans, query_max(root, pos[top[l]], pos[l]));

            l = fa[top[l]];

      }

      //if (l == r) return Ans;

      if (dep[l] > dep[r]) swap(l, r);

      Ans = max(Ans, query_max(root, pos[l], pos[r]));

      return Ans;

 }

 int QSUM(int l, int r){

      int sum = ;

      while (top[l] != top[r]){

            //低的往上爬

            if (dep[top[l]] < dep[top[r]]) swap(l, r);

            sum += query_sum(root, pos[top[l]], pos[l]);

            l = fa[top[l]];

      }

      //if (l == r) return sum;

      if (dep[l] > dep[r]) swap(l, r);

      sum += query_sum(root, pos[l], pos[r]);

      return sum;

 }

 void work(){

      int q;

      scanf("%d", &q);

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

          char str[];

          scanf("%s", str);

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

             int l, x;

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

             change(root, pos[l], x);

          }else{

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

                   int l, r;

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

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

                }else{

                   int l, r;

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

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

                }

          }

      }

 }

 int main(){

     int T;

     init();

     work();

     return ;

 }

码农公寓