P1505 [国家集训队]旅游

题目描述

Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。

Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。

现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。

输入输出格式

输入格式：

输入的第一行包含一个整数N，表示T 城中的景点个数。景点编号为 0...N − 1。

接下来N − 1 行，每行三个整数u、v 和w，表示有一条u 到v，使 Ray 愉悦度增加w 的桥。桥的编号为1...N − 1。|w| <= 1000。输入的第N + 1 行包含一个整数M，表示Ray 的操作数目。

接下来有M 行，每行描述了一个操作，操作有如下五种形式：

C i w，表示Ray 对于经过第i 座桥的愉悦度变成了w。
N u v，表示Ray 对于经过景点u 到v 的路径上的每一座桥的愉悦度都变成原来的相反数。
SUM u v，表示询问从景点u 到v 所获得的总愉悦度。
MAX u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最大愉悦度。
MIN u v，表示询问从景点u 到v 的路径上的所有桥中某一座桥所提供的最小愉悦度。

测试数据保证，任意时刻，Ray 对于经过每一座桥的愉悦度的绝对值小于等于1000。

输出格式：

对于每一个询问(操作S、MAX 和MIN)，输出答案。

输入输出样例

输入样例#1：复制

3
0 1 1
1 2 2
8
SUM 0 2
MAX 0 2
N 0 1
SUM 0 2
MIN 0 2
C 1 3
SUM 0 2
MAX 0 2

输出样例#1：复制

说明

很容易的基础题哦>.<

吐槽

这是国家集训队的题目啊，还基础题！！！

思路

做了三四道树剖，这题算是技巧性较高的了。。

看了看其他大佬的题解，感觉有些难的地方根本就没解释啊，故写文以记之。

这题难点有二：

正常模板为点权，此题是边权

由于一个点有多个儿子，但只有一个父亲，易想到将原点权代替成与父亲的边权处理。1号节点边权为0。

既然对于边权维护硬核转换为点权，则在树链上反复跳的时候,LCA点的权值是不能取的，因为LCA维护的是与他父亲的边权，u与v的路径上并不经过。

此外的话对于操作C你在修改一条单边的时候，应当选择深度大的节点（只有深度大的节点维护的边权才是U,V间的边权），其中需要额外加一个判断。

线段树的懒标记下放

我们可以设

对于

此外就是一些树剖基本操作啦，最后注意求最小值的时候初值不能为0，题目会出现负数。。

还有一个要我至死铭记的东西判断里是==不是=

所有树剖都必错的点

  1 #include<bits/stdc++.h>
  2 #define stop system("pause")
  3 #define INF 2000000000
  4 
  5 using namespace std;
  6 const int maxn=1e6+10;
  7 struct Edge
  8 {
  9     int u, v, next, value;
 10 }way[maxn << 1];
 11 struct tree
 12 {
 13     int l, r, value, maxn, minn, f;
 14 }p[maxn << 2];
 15 
 16 int head[maxn];
 17 int top[maxn];
 18 int father[maxn];
 19 int  son[maxn];
 20 int size[maxn];
 21 int tuop[maxn];
 22 int pre[maxn];
 23 int deep[maxn];
 24 int w[maxn];
 25 char fh[10];
 26 int tot = 0, cur = 0;
 27 int n, m, ans;
 28 
 29 inline int read()
 30 {
 31     int f = 0, fu = 1;
 32     char c = getchar();
 33     while(c < '0' || c > '9')
 34     {
 35         if(c == '-') fu = -1;
 36         c = getchar();
 37     }
 38     while(c >= '0' && c <= '9')
 39     {
 40         f = (f << 3) + (f << 1) + c - 48;
 41         c = getchar();
 42     }
 43     return f * fu;
 44 }
 45 int add(int x,int y,int w)
 46 {
 47     way[++tot].next=head[x];
 48    way[tot].v=y;
 49     way[tot].value=w;
 50     head[x]=tot;
 51 }
 52 inline void dfs1(int u)
 53 {
 54     size[u] = 1;
 55     for(int i = head[u]; i; i = way[i].next)
 56     {
 57         int v = way[i].v;
 58         if(v == father[u]) continue;
 59         deep[v] = deep[u] + 1;
 60         w[v] = way[i].value;
 61         father[v] = u;
 62         dfs1(v);
 63         size[u] += size[v];
 64         if(size[v] > size[son[u]]) son[u] = v;
 65     }
 66 }
 67 int dfs2(int x,int tp)
 68 {
 69     top[x]=tp;
 70     tuop[x]=++cur;
 71     pre[cur]=x;
 72     if(son[x])
 73     {
 74         dfs2(son[x],tp);
 75     }
 76     for(int i=head[x];i;i=way[i].next)
 77     {
 78         int to=way[i].v;
 79         if(to==father[x]||to==son[x])
 80         {
 81             continue;
 82         }
 83         dfs2(to,to);
 84     }
 85 }
 86 int lazy(int x)
 87 {
 88     p[x<<1].f=(p[x].f+p[x<<1].f)%2;
 89     p[x<<1|1].f=(p[x].f+p[x<<1|1].f)%2;
 90     p[x<<1].value=-p[x<<1].value;
 91     p[x<<1|1].value=-p[x<<1|1].value;
 92     swap(p[x<<1].maxn,p[x<<1].minn);
 93     p[x<<1].maxn=p[x<<1].maxn*-1;
 94     p[x<<1].minn=p[x<<1].minn*-1;
 95     swap(p[x<<1|1].maxn,p[x<<1|1].minn );
 96     p[x<<1|1].maxn*=-1;
 97     p[x<<1|1].minn*=-1;
 98     p[x].f=0;
 99 }
100 
101 int update(int x)
102 {
103     p[x].value=p[x<<1].value+p[x<<1|1].value;
104     p[x].maxn=max(p[x<<1].maxn,p[x<<1|1].maxn);
105     p[x].minn =min(p[x<<1].minn,p[x<<1|1].minn);
106 }
107 void create(int x,int l,int r)
108 {
109     p[x].l=l;
110     p[x].r=r;
111     p[x].f=0;
112     if(l==r)
113     {
114         p[x].value=w[pre[l]];
115         p[x].maxn=w[pre[l]];
116         p[x].minn=w[pre[l]];
117         return ;
118     }
119     int mid=(l+r)>>1;
120     create(x<<1,l,mid);
121     create(x<<1|1,mid+1,r);
122     update(x);
123 }
124 void change_point(int x,int l,int r)
125 {
126     if(p[x].l==p[x].r)
127     {
128         p[x].value=r;
129         p[x].maxn=r;
130         p[x].minn=r;
131         return ;
132     }
133     if(p[x].f)
134     {
135         lazy(x);
136     }
137     int mid=(p[x].l+p[x].r)>>1;
138     if(l<=mid)
139     {
140         change_point(x<<1,l,r);
141     }
142     else
143     {
144         change_point(x<<1|1,l,r);
145     }
146     update(x);
147 }
148 
149 void change_line(int x,int l,int r)
150 {
151     if(p[x].l>=l&&p[x].r<=r)
152     {
153         p[x].f++;
154         p[x].f%=2;
155         p[x].value*=-1;
156         swap(p[x].maxn,p[x].minn);
157         p[x].maxn*=-1;
158         p[x].minn*=-1;
159         return ;
160      } 
161      if(p[x].f)
162      {
163          lazy(x);
164      }
165      int mid=(p[x].l+p[x].r)>>1;
166      if(l<=mid)
167      change_line(x<<1,l,r);
168      if(r>mid)
169      {
170          change_line(x<<1|1,l,r);
171      }
172      update(x);
173 } 
174 inline void ask_sum(int x,int l,int r)
175 {
176     if(p[x].l>=l&&p[x].r<=r)
177     {
178         ans+=p[x].value;
179         return ;
180     }
181     if(p[x].f)
182     {
183         lazy(x);
184     }
185     int mid=(p[x].l+p[x].r)>>1;
186     if(l<=mid)
187     {
188         ask_sum(x<<1,l,r);
189     }
190     if(r>mid)
191     {
192         ask_sum(x<<1|1,l,r);
193     }
194     update(x);
195 }
196 inline void ask_min(int x,int l,int r)
197 {
198     if(p[x].l>=l&&p[x].r<=r)
199     {
200         ans=min(ans,p[x].minn);
201         return;
202     }
203     if(p[x].f)
204     {
205         lazy(x);
206     }
207     int mid=(p[x].l+p[x].r)>>1;
208     if(l<=mid)
209     {
210         ask_min(x<<1,l,r);
211     }
212     if(r>mid)
213     {
214         ask_min(x<<1|1,l,r);
215     }
216     update(x);
217 }
218 
219 inline void ask_max(int x,int l,int r)
220 {
221     if(p[x].l>=l&&p[x].r<=r)
222     {
223         ans=max(ans,p[x].maxn);
224         return ;
225     }
226     if(p[x].f)
227     {
228         lazy(x);
229     }
230     int mid=(p[x].l+p[x].r)>>1;
231     if(l<=mid)
232     {
233         ask_max(x<<1,l,r);
234     }
235     if(r>mid)
236     {
237        ask_max(x<<1|1,l,r);
238     }
239     update(x);
240 }
241 void qsum(int x,int to)
242 {
243     ans=0;
244     while(top[x]!=top[to])
245     {
246         if(deep[top[x]]<deep[top[to]])
247         {
248             swap(x,to);    
249         }
250         ask_sum(1,tuop[top[x]],tuop[x]);
251         x=father[top[x]];
252     }
253     if(x==to)
254     return ;
255     if(tuop[x]>tuop[to])
256     {
257         swap(x,to);
258     }
259     ask_sum(1,tuop[x]+1,tuop[to]);
260 }
261 
262 void qmin(int x,int to)
263 {
264     ans=INF;
265     while(top[x]!=top[to])
266     {
267         if(deep[top[x]]<deep[top[to]])
268         {
269             swap(x,to);
270         }
271         ask_min(1,tuop[top[x]],tuop[x]);
272         x=father[top[x]];
273     }
274     if(x==to)
275     return ;
276     if(tuop[x]>tuop[to])
277     {
278         swap(x,to);
279     }
280     ask_min(1,tuop[x]+1,tuop[to]);
281 }
282 
283 inline void qmax(int x,int to)
284 {
285     ans=-INF;
286     while(top[x]!=top[to])
287     {
288         if(deep[top[x]]<deep[top[to]])
289         {
290             swap(x,to);
291         }
292         ask_max(1,tuop[top[x]],tuop[x]);
293         x=father[top[x]];
294     }
295     if(x==to)
296     return ;
297     if(tuop[x]>tuop[to])
298     {
299         swap(x,to);
300     }
301     ask_max(1,tuop[x]+1,tuop[to]);
302 }
303 inline void flip(int x,int to)
304 {
305     while(top[x]!=top[to])
306     {
307         if(deep[top[x]]<deep[top[to]])
308         {
309             swap(x,to);
310         }
311         change_line(1,tuop[top[x]],tuop[x]);
312         x=father[top[x]];
313     }
314     if(x==to)
315     return ;
316     if(tuop[x]>tuop[to])
317     {
318         swap(x,to);
319     }
320     change_line(1,tuop[x]+1,tuop[to]);
321 }
322 int main()
323 {
324     cin>>n;
325     for(int i=1;i<n;i++)
326     {
327         int a,b,c;
328         cin>>a>>b>>c;
329         a++,b++;
330         add(a,b,c);
331         add(b,a,c);
332     }
333     dfs1(1);
334     dfs2(1,1);
335     create(1,1,n);
336     cin>>m;
337     for(int i=1;i<=m;i++)
338     {
339         scanf("%s",&fh);
340         if(fh[0]=='C')
341         {
342             int a,b;
343             cin>>a>>b;
344             a++;
345             change_point(1,tuop[a],b);
346         }
347         else
348         if(fh[0]=='N')
349         {
350             int a,b;
351             cin>>a>>b;
352             a++,b++;
353             flip(a,b);
354         }
355         else
356         if(fh[0]=='S')
357         {
358             int a,b;
359             cin>>a>>b;
360             a++,b++;
361             qsum(a,b);
362             cout<<ans<<endl;
363         }
364         else
365         if(fh[1]=='I')
366         {
367             int a,b;
368             cin>>a>>b;
369             a++,b++;
370             qmin(a,b);
371             cout<<ans<<endl;
372         }
373         else
374         {
375             int a,b;
376             cin>>a>>b;
377             a++,b++;
378             qmax(a,b);
379             cout<<ans<<endl;
380         }
381     }
382     
383     return 0;
384 }