题目链接：https://www.luogu.org/problem/P4315

 

 

思路：

我们发现，一个点最多只有一个父亲结点，那么我们就可以考虑把这个点与其父亲结点之间边的边权转化为这个点的点权！那，之后，就变成了我们一开始说的树链剖分裸题了呀！还有一个非常重要的细节就是树链剖分查询和修改路径的时候，父亲结点是不在路径上的！因为父亲结点的点权代表的是它与它的父亲之间的边权，因此，在查询和修改的时候，最后左端点为dfn[x] + 1

 

  1 // luogu-judger-enable-o2
  2 #include <stdio.h>
  3 #include <algorithm>
  4 #include <iostream>
  5 #include <stdbool.h>
  6 #include <stdlib.h>
  7 #include <string>
  8 #include <string.h>
  9 #include <stack>
 10 #include <queue>
 11 #include <set>
 12 #include <map>
 13 #include <math.h>
 14 
 15 #define INF 0x3f3f3f3f
 16 #define LL long long
 17 using namespace std;
 18 
 19 const int maxn = 300100;
 20 
 21 struct Edge{
 22     int to,next,w;
 23 }edge[maxn*4];
 24 
 25 int head[maxn],tot;
 26 int arr[maxn];
 27 
 28 void add_edge(int u,int v,int w){
 29     edge[++tot] = Edge{v,head[u],w};
 30     head[u] = tot;
 31 }
 32 
 33 int p[maxn];
 34 int fa[maxn];
 35 int siz[maxn];
 36 int dep[maxn];
 37 int son[maxn];
 38 
 39 void dfs1(int u,int f){
 40     siz[u] = 1;
 41     fa[u] = f;
 42     dep[u] = dep[f] + 1;
 43     for (int i=head[u];~i;i=edge[i].next){
 44         int v = edge[i].to;
 45         if (v == f)
 46             continue;
 47         p[v] = edge[i].w;
 48         dfs1(v, u);
 49         siz[u] += siz[v];
 50         if (siz[son[u]] < siz[v])
 51             son[u] = v;
 52     }
 53 }
 54 
 55 
 56 int tim;
 57 int dfn[maxn];
 58 int top[maxn];
 59 
 60 void dfs2(int u,int t){
 61     dfn[u] = ++tim;
 62     top[u] = t;
 63     arr[tim] = p[u];
 64     if (!son[u]){
 65         return ;
 66     }
 67     dfs2(son[u],t);
 68     for (int i=head[u];~i;i=edge[i].next){
 69         int v = edge[i].to;
 70         if (v == fa[u] || v == son[u]){
 71             continue;
 72         }
 73         dfs2(v,v);
 74     }
 75 }
 76 
 77 
 78 struct segment_tree{
 79     int l,r;
 80     LL maxval;
 81     int lazy;
 82     int tag;
 83 }tree[maxn*4];
 84 
 85 void pushup(int nod){
 86     tree[nod].maxval = max(tree[nod<<1].maxval,tree[(nod<<1)+1].maxval);
 87 }
 88 
 89 void pushdown(int nod){
 90     if (tree[nod].tag >= 0){
 91         tree[nod<<1].lazy = tree[(nod<<1)+1].lazy = 0;
 92         tree[nod<<1].maxval = tree[(nod<<1)+1].maxval = tree[nod<<1].tag = tree[(nod<<1)+1].tag = tree[nod].tag;
 93         tree[nod].tag = -1;
 94     }
 95     if (tree[nod].lazy){
 96         tree[nod<<1].lazy += tree[nod].lazy;
 97         tree[(nod<<1)+1].lazy += tree[nod].lazy;
 98         tree[nod<<1].maxval += tree[nod].lazy;
 99         tree[(nod<<1)+1].maxval += tree[nod].lazy;
100         tree[nod].lazy = 0;
101     }
102 }
103 
104 void build (int l,int r,int nod){
105     tree[nod].tag = -1;
106     tree[nod].l = l;
107     tree[nod].r = r;
108     if ( l == r){
109         tree[nod].maxval = arr[l];
110         return ;
111     }
112     int mid = (l + r) >> 1;
113     build(l,mid,nod<<1);
114     build(mid+1,r,(nod<<1)+1);
115     pushup(nod);
116 }
117 
118 
119 void modify1(int x,int y,int z,int k=1){
120     int l = tree[k].l, r = tree[k].r;
121     if (x <= l && y >= r){
122         tree[k].maxval += z;
123         tree[k].lazy += z;
124         return ;
125     }
126     pushdown(k);
127     int mid = (l + r) >> 1;
128     if (x <= mid){
129         modify1(x,y,z,k<<1);
130     }
131     if (y > mid){
132         modify1(x,y,z,(k<<1)+1);
133     }
134     pushup(k);
135 }
136 
137 
138 void modify2(int x,int y,int z,int k=1){
139     int l = tree[k].l,r = tree[k].r;
140     if (x <= l && y >= r){
141         tree[k].maxval = tree[k].tag = z;
142         tree[k].lazy = 0;
143         return ;
144     }
145     pushdown(k);
146     int mid = (l + r) >> 1;
147     if (x <= mid) {
148         modify2(x,y,z,k<<1);
149     }
150     if (y > mid){
151         modify2(x,y,z,(k<<1)+1);
152     }
153     pushup(k);
154 }
155 
156 LL cmax(int x,int y,int k=1){
157     int l = tree[k].l,r = tree[k].r;
158     if (x <= l && y >= r){
159         return tree[k].maxval;
160     }
161     pushdown(k);
162     int mid = (l + r) >> 1;
163     LL ret = 0;
164     if (x <= mid){
165         ret = max(ret,cmax(x,y,k<<1));
166     }
167     if (y > mid){
168         ret = max(ret,cmax(x,y,(k<<1)+1));
169     }
170     return ret;
171 }
172 
173 
174 void mchain1(int x,int y,int z){
175     while (top[x] != top[y]){
176         if (dep[top[x]] < dep[top[y]])
177             swap(x,y);
178         modify1(dfn[top[x]],dfn[x],z);
179         x = fa[top[x]];
180     }
181     if (dep[x] > dep[y])
182         swap(x,y);
183     modify1(dfn[x]+1,dfn[y],z);
184 }
185 
186 
187 void mchain2(int x,int y,int z){
188     while (top[x] != top[y]){
189         if (dep[top[x]] < dep[top[y]])
190             swap(x,y);
191         modify2(dfn[top[x]],dfn[x],z);
192         x = fa[top[x]];
193     }
194     if (dep[x] > dep[y])
195         swap(x,y);
196     modify2(dfn[x]+1,dfn[y],z);
197 }
198 
199 
200 
201 LL query_max(int x,int y){
202     LL ret = 0;
203     while (top[x] != top[y]){
204         if (dep[top[x]] < dep[top[y]])
205             swap(x,y);
206         ret = max(ret,cmax(dfn[top[x]],dfn[x],1));
207         x = fa[top[x]];
208     }
209     if (dep[x] > dep[y])
210         swap(x,y);
211     ret = max(ret,cmax(dfn[x]+1,dfn[y],1));
212     return ret;
213 }
214 
215 int main(){
216     int n;
217     scanf("%d",&n);
218     memset(head,-1, sizeof(head));
219     for (int i=1;i<=n-1;i++){
220         int x,y,z;
221         scanf("%d%d%d",&x,&y,&z);
222         add_edge(x,y,z);
223         add_edge(y,x,z);
224     }
225     dfs1(1,0);
226     dfs2(1,1);
227     build(1,n,1);
228     char s[10];
229     int x,y,z;
230     while (~scanf("%s",s)) {
231         if (strcmp(s, "Stop") == 0)
232             break;
233         if (strcmp(s, "Cover") == 0) {
234             scanf("%d%d%d", &x , &y, &z);
235             mchain2(x,y,z);
236         } else if (strcmp(s, "Add") == 0) {
237             scanf("%d%d%d", &x , &y, &z);
238             mchain1(x,y,z);
239         } else if (strcmp(s, "Change") == 0) {
240             scanf("%d%d", &x, &z);
241             if (dep[edge[2*x-1].to] < dep[edge[2*x].to] ){
242                 x = edge[2*x].to;
243             }
244             else
245                 x = edge[2*x-1].to;
246             modify2(dfn[x],dfn[x],z);
247         }
248         else if (strcmp(s, "Max") == 0){
249             scanf("%d%d",&x,&y);
250             printf("%lld\n",query_max(x,y));
251         }
252     }
253     return 0;
254 }