1036: [ZJOI2008]树的统计Count （树链剖分）

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 3401 Solved: 1418
[Submit][Status]

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

入门题

 /* **********************************************

 Author      : kuangbin

 Created Time: 2013/8/12 21:58:47

 File Name   : F:\2013ACM练习\专题学习\数链剖分\树的统计Count.cpp

 *********************************************** */

 #include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 #include <vector>

 #include <queue>

 #include <set>

 #include <map>

 #include <string>

 #include <math.h>

 #include <stdlib.h>

 using namespace std;

 const int MAXN = ;

 struct Edge

 {

     int to,next;

 }edge[MAXN*];

 int head[MAXN],tot;

 int top[MAXN]; //top[v] 表示v所在的重链的顶端节点

 int fa[MAXN]; //父亲节点

 int deep[MAXN];//深度

 int num[MAXN]; //num[v]表示以v为根的子树的节点数

 int p[MAXN]; //p[v]表示v在线段树中的位置

 int fp[MAXN];//和p数组相反

 int son[MAXN];//重儿子

 int pos;

 void init()

 {

     tot = ;

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

     pos = ;

     memset(son,-,sizeof(son));

 }

 void addedge(int u,int v)

 {

     edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;

 }

 void dfs1(int u,int pre,int d) //第一遍dfs求出fa,deep,num,son

 {

     deep[u] = d;

     fa[u] = pre;

     num[u] = ;

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

     {

         int v = edge[i].to;

         if(v != pre)

         {

             dfs1(v,u,d+);

             num[u] += num[v];

             if(son[u] == - || num[v] > num[son[u]])

                 son[u] = v;

         }

     }

 }

 void getpos(int u,int sp)

 {

     top[u] = sp;

     p[u] = pos++;

     fp[p[u]] = u;

     if(son[u] == -) return;

     getpos(son[u],sp);

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

     {

         int v = edge[i].to;

         if(v != son[u] && v != fa[u]) getpos(v,v);

     }

 }

 struct Node

 {

     int l,r;

     int sum;

     int Max;

 }segTree[MAXN*];

 void push_up(int i)

 {

     segTree[i].sum = segTree[i<<].sum + segTree[(i<<)|].sum;

     segTree[i].Max = max(segTree[i<<].Max,segTree[(i<<)|].Max);

 }

 int s[MAXN];

 void build(int i,int l,int r)

 {

     segTree[i].l = l;

     segTree[i].r = r;

     if(l == r)

     {

         segTree[i].sum = segTree[i].Max = s[fp[l]];

         return ;

     }

     int mid = (l + r)/;

     build(i<<,l,mid);

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

     push_up(i);

 }

 void update(int i,int k,int val)//更新线段树的第k个值为val

 {

     if(segTree[i].l == k && segTree[i].r == k)

     {

         segTree[i].sum = segTree[i].Max = val;

         return;

     }

     int mid = (segTree[i].l + segTree[i].r)/;

     if(k <= mid)update(i<<,k,val);

     else update((i<<)|,k,val);

     push_up(i);

 }

 int queryMax(int i,int l,int r)//查询线段树[l,r]区间的最大值

 {

     if(segTree[i].l == l && segTree[i].r == r)

     {

         return segTree[i].Max;

     }

     int mid = (segTree[i].l + segTree[i].r)/;

     if(r <= mid) return queryMax(i<<,l,r);

     else if(l > mid)return queryMax((i<<)|,l,r);

     else return max(queryMax(i<<,l,mid),queryMax((i<<)|,mid+,r));

 }

 int querySum(int i,int l,int r) //查询线段树[l,r]区间的和

 {

     if(segTree[i].l == l && segTree[i].r == r)

         return segTree[i].sum;

     int mid = (segTree[i].l + segTree[i].r)/;

     if(r <= mid)return querySum(i<<,l,r);

     else if(l > mid)return querySum((i<<)|,l,r);

     else return querySum(i<<,l,mid) + querySum((i<<)|,mid+,r);

 }

 int findMax(int u,int v)//查询u->v路径上节点的最大权值

 {

     int f1 = top[u] , f2 = top[v];

     int tmp = -;

     while(f1 != f2)

     {

         if(deep[f1] < deep[f2])

         {

             swap(f1,f2);

             swap(u,v);

         }

         tmp = max(tmp,queryMax(,p[f1],p[u]));

         u = fa[f1];

         f1 = top[u];

     }

     if(deep[u] > deep[v]) swap(u,v);

     return max(tmp,queryMax(,p[u],p[v]));

 }

 int findSum(int u,int v) //查询u->v路径上节点的权值的和

 {

     int f1 = top[u], f2 = top[v];

     int tmp = ;

     while(f1 != f2)

     {

         if(deep[f1] < deep[f2])

         {

             swap(f1,f2);

             swap(u,v);

         }

         tmp += querySum(,p[f1],p[u]);

         u = fa[f1];

         f1 = top[u];

     }

     if(deep[u] > deep[v]) swap(u,v);

     return tmp + querySum(,p[u],p[v]);

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     int n;

     int q;

     char op[];

     int u,v;

     while(scanf("%d",&n) == )

     {

         init();

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

         {

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

             addedge(u,v);

             addedge(v,u);

         }

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

             scanf("%d",&s[i]);

         dfs1(,,);

         getpos(,);

         build(,,pos-);

         scanf("%d",&q);

         while(q--)

         {

             scanf("%s%d%d",op,&u,&v);

             if(op[] == 'C')

                 update(,p[u],v);//修改单点的值

             else if(strcmp(op,"QMAX") == )

                 printf("%d\n",findMax(u,v));//查询u->v路径上点权的最大值

             else printf("%d\n",findSum(u,v));//查询路径上点权的和

         }

     }

     return ;

 }

巴特西

1036: [ZJOI2008]树的统计Count （树链剖分）