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
题解：
树链剖分模板～
第一次自己写，终于写过了
修改对应到线段树中的单点修改，查询就是不断向上跳top直到两个点在同一条链上，最后再”跳“一次把两个点跳到一起，过程中通过线段树求和与最大值
注意：1.题目中说n<=30000，但实际不是这样，会RE！！！n的范围需要调大一些
2.结点值可能为负！求路径上MAX时最先赋值应为-INF
3.建双向边时数组大小要开2*MAXN
代码：
1 #include<iostream>
2 #include<cstdio>
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]<
dep[f2]) swap(f1,f2),swap(x,y);
115 ret=
max(ret,query_Max(root,rank[f1],rank[x]));
116 x=fa[top[x]];f1=
top[x];
117 }
118 if(dep[x]<
dep[y]) swap(x,y);
119 return max(ret,query_Max(root,rank[y],rank[x]));
120 }
121 int Sum(
int x,
int y)
122 {
123 int ret=
0;
124 int f1=top[x],f2=
top[y];
125 while(f1!=
f2)
126 {
127 if(dep[f1]<
dep[f2]) swap(f1,f2),swap(x,y);
128 ret+=
query_Sum(root,rank[f1],rank[x]);
129 x=fa[top[x]];f1=
top[x];
130 }
131 if(dep[x]<
dep[y]) swap(x,y);
132 return ret+
query_Sum(root,rank[y],rank[x]);
133 }
134
135 int main()
136 {
137 int n,q,i,a,b;
138 char ch[
10];
139 scanf(
"%d",&
n);
140 for(i=
1;i<n;i++
)
141 scanf(
"%d%d",&a,&
b),addedge(a,b);
142 for(i=
1;i<=n;i++) scanf(
"%d",&
val[i]);
143
144 dfs1(
1);
145 rank[
1]=
1;tot=
1;top[
1]=
1;w[
1]=val[
1];
146 dfs2(
1);
147 root=&t[++
cnt1];
148 Build_Tree(root,
1,n);
149
150 scanf(
"%d",&
q);
151 while(q -->
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 }
View Code
转载于:https://www.cnblogs.com/lindalee/p/7209984.html
相关资源：DirectX修复工具V4.0增强版
