1036. [ZJOI2008]树的统计【树链剖分】-白红宇

1036. [ZJOI2008]树的统计【树链剖分】

阅读量：7079 次

发布时间：2019-06-28

本文共 4470 字，大约阅读时间需要 14 分钟。

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

1 2

2 3

4 1

4 2 1 3

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

树链剖分模板

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6   7 int head[30001],num_edge;  8 int Father[30001],Weight[30001];  9 int Son[30001],Top[30001]; 10 int T_NUM[30001],a[30001]; 11 int Depth[30001]; 12 int sum,n,INF,ans; 13 int TREE[30001]; 14 char st[101]; 15 struct node 16 { 17     int to,next; 18 } edge[60005]; 19 struct node1 20 { 21     int max,sum; 22 } Segt[120001]; 23 void add(int u,int v) 24 { 25     edge[++num_edge].to=v; 26     edge[num_edge].next=head[u]; 27     head[u]=num_edge; 28 } 29 void dfs1(int x) 30 { 31     Weight[x]=1; 32     Depth[x]=Depth[Father[x]]+1; 33     for (int i=head[x]; i!=0; i=edge[i].next) 34         if (edge[i].to!=Father[x]) 35         { 36             Father[edge[i].to]=x; 37             dfs1(edge[i].to); 38             Weight[x]+=Weight[edge[i].to]; 39             if (Son[x]==0 || Weight[edge[i].to]>Weight[Son[x]]) 40                 Son[x]=edge[i].to; 41         } 42 } 43  44 void dfs2(int x,int tp) 45 { 46     T_NUM[x]=++sum; 47     TREE[sum]=a[x]; 48     Top[x]=tp; 49     if (Son[x]!=0) 50         dfs2(Son[x],tp); 51     for (int i=head[x]; i!=0; i=edge[i].next) 52         if (edge[i].to!=Son[x] && edge[i].to!=Father[x]) 53             dfs2(edge[i].to,edge[i].to); 54 } 55  56 void Build(int node,int l,int r,int a[]) 57 { 58     if (l==r) 59         Segt[node].max=Segt[node].sum=a[l]; 60     else 61     { 62         int mid=(l+r)/2; 63         Build(node*2,l,mid,a); 64         Build(node*2+1,mid+1,r,a); 65         Segt[node].max=max(Segt[node*2].max,Segt[node*2+1].max); 66         Segt[node].sum=Segt[node*2].sum+Segt[node*2+1].sum; 67     } 68 } 69  70 void Update(int node,int l,int r,int x,int k) 71 { 72     if (l==r) 73         Segt[node].max=Segt[node].sum=k; 74     else 75     { 76         mid=(l+r)/2; 77         (x<=mid) 78         date(node*2,l,mid,x,k); 79         else 80             Update(node*2+1,mid+1,r,x,k); 81         Segt[node].max=max(Segt[node*2].max,Segt[node*2+1].max); 82         Segt[node].sum=Segt[node*2].sum+Segt[node*2+1].sum; 83     } 84 } 85  86 int QueryMax(int node,int l,int r,int l1,int r1) 87 { 88     if (r
         
          r1) 89         return -INF; 90     if (l1<=l && r<=r1) 91         return Segt[node].max; 92     int mid=(l+r)/2; 93     return max(QueryMax(node*2,l,mid,l1,r1), 94                QueryMax(node*2+1,mid+1,r,l1,r1)); 95 } 96  97 int QuerySum(int node,int l,int r,int l1,int r1) 98 { 99     if (r
          
           r1)100 return 0;101 if (l1<=l && r<=r1)102 return Segt[node].sum;103 int mid=(l+r)/2;104 return QuerySum(node*2,l,mid,l1,r1)+105 QuerySum(node*2+1,mid+1,r,l1,r1);106 }107 108 int GetSum(int x,int y)109 {110 int fx,fy;111 memset(&ans,0,sizeof(ans));112 fx=Top[x];113 fy=Top[y];114 while (fx!=fy)115 {116 if (Depth[fx]
           
            Depth[y]) swap(x,y);122 return ans+=QuerySum(1,1,n,T_NUM[x],T_NUM[y]);123 }124 125 int GetMax(int x,int y)126 {127 int fy,fx;128 memset(&ans,-0x7f,sizeof(ans));129 fx=Top[x];130 fy=Top[y];131 while (fx!=fy)132 {133 if (Depth[fx]
            
             Depth[y]) swap(x,y);139 return max(ans,QueryMax(1,1,n,T_NUM[x],T_NUM[y]));140 }141 142 int main()143 {144 int i,u,v,l,m,x,y;145 memset(&INF,0x7f,sizeof(INF));146 scanf("%d",&n);147 for (i=1; i<=n-1; ++i)148 {149 scanf("%d%d",&u,&v);150 add(u,v);151 add(v,u);152 }153 for (int i=1; i<=n; ++i)154 scanf("%d",&a[i]);155 Depth[1]=1;156 dfs1(1);157 dfs2(1,1);//两边预处理158 Build(1,1,n,TREE);//TREE数组保存用来建线段树的区间159 scanf("%d",&m);160 for (int i=1; i<=m; ++i)161 {162 scanf("%s%d%d",&st,&x,&y);163 if (st[1]=='H')164 Update(1,1,n,T_NUM[x],y);165 if (st[1]=='M')166 printf("%d\n",GetMax(x,y));167 if (st[1]=='S')168 printf("%d\n",GetSum(x,y));169 }170 }