Description

　　一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成

一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I

II. 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

 

题解：

树链剖分模板～

第一次自己写，终于写过了

修改对应到线段树中的单点修改，查询就是不断向上跳top直到两个点在同一条链上，最后再”跳“一次把两个点跳到一起，过程中通过线段树求和与最大值

 

注意：1.题目中说n<=30000，但实际不是这样，会RE！！！n的范围需要调大一些

2.结点值可能为负！求路径上MAX时最先赋值应为-INF

3.建双向边时数组大小要开2*MAXN

 

代码：

1 #include
       
          2 #include
        
           3 #define INF 2147483647  4 using namespace std;  5   6 const int MAXN=1000005;  7 struct node  8 {  9     int v; 10     node *next;        11 }pool[MAXN],*h[MAXN]; 12 int cnt,tot; 13 int val[MAXN],fa[MAXN],size[MAXN],son[MAXN],dep[MAXN],top[MAXN],w[MAXN],rank[MAXN]; 14  15 void addedge(int u,int v) 16 { 17     node *p=&pool[++cnt],*q=&pool[++cnt]; 18     p->v=v;p->next=h[u];h[u]=p; 19     q->v=u;q->next=h[v];h[v]=q; 20 } 21 void dfs1(int u) //GET fa[],size[],dep[],son[] 22 { 23     int v; 24     size[u]=1; 25     int Bson=0,sonnum=0; 26     for(node *p=h[u];p;p=p->next) 27         if(fa[u]!=(v=p->v)) 28         { 29             fa[v]=u; 30             dep[v]=dep[u]+1; 31             dfs1(v); 32             size[u]+=size[v]; 33             if(size[v]>Bson) Bson=size[v],sonnum=v;                  34         } 35     son[u]=sonnum; 36 } 37 void dfs2(int u) //GET top[],w[],rank[] 38 { 39     int v=son[u]; 40     if(v) 41     { 42         top[v]=top[u]; 43         rank[v]=++tot; 44         w[rank[v]]=val[v]; 45         dfs2(v); 46     } 47     for(node *p=h[u];p;p=p->next) 48         if(fa[v=p->v]==u && v!=son[u]) 49         { 50             top[v]=v; 51             rank[v]=++tot; 52             w[rank[v]]=val[v]; 53             dfs2(v);                  54         } 55 } 56  57 struct tree 58 { 59     int l,r,sum,Max; 60     tree *left,*right;        61 }t[3*MAXN],*root; 62 int cnt1; 63 void Build_Tree(tree *p,int l,int r) 64 { 65     p->l=l;p->r=r; 66     if(l==r) 67     { 68         p->sum=p->Max=w[l]; 69         return; 70     } 71     tree *left=&t[++cnt1],*right=&t[++cnt1]; 72     p->left=left;p->right=right; 73     int mid=(l+r)/2; 74     Build_Tree(p->left,l,mid); 75     Build_Tree(p->right,mid+1,r); 76     p->sum=p->left->sum+p->right->sum; 77     p->Max=max(p->left->Max,p->right->Max); 78 } 79 void change(tree *p,int l,int r,int c) 80 { 81     if(p->l==l && p->r==r) 82     { 83         p->sum=p->Max=c; 84         return;            85     } 86     if(p->left->r>=r) change(p->left,l,r,c); 87     else if(p->right->l<=l) change(p->right,l,r,c); 88     p->sum=p->left->sum+p->right->sum; 89     p->Max=max(p->left->Max,p->right->Max); 90 } 91 int query_Max(tree *p,int l,int r) 92 { 93     if(p->l==l && p->r==r) 94         return p->Max; 95     if(p->left->r>=r) return query_Max(p->left,l,r); 96     else if(p->right->l<=l) return query_Max(p->right,l,r); 97     else return max(query_Max(p->left,l,p->left->r),query_Max(p->right,p->right->l,r)); 98 } 99 int query_Sum(tree *p,int l,int r)100 {101     if(p->l==l && p->r==r)102         return p->sum;103     if(p->left->r>=r) return query_Sum(p->left,l,r);104     else if(p->right->l<=l) return query_Sum(p->right,l,r);105     else return query_Sum(p->left,l,p->left->r)+query_Sum(p->right,p->right->l,r);106 }107 108 int Max(int x,int y)109 {110     int ret=-INF;111     int f1=top[x],f2=top[y];112     while(f1!=f2)113     {114         if(dep[f1]
         
           0)152     {153         scanf("%s",ch);scanf("%d%d",&a,&b);154         if(ch[1]=='H')155             change(root,rank[a],rank[a],b);156         else if(ch[1]=='M')157             printf("%d\n",Max(a,b));158         else printf("%d\n",Sum(a,b));159     }160     161     return 0;162 }