<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<style type="text/css">
body{ font-size:10px; }
</style>
</head>
<body>
<title>Problem 2157. -- 旅游</title><center><h2>2157: 旅游</h2><span class=green>Time Limit: </span>10 Sec <span class=green>Memory Limit: </span>259 MB<br><span class=green>Submit: </span>794 <span class=green>Solved: </span>413<br></center><h2>Description</h2><div class=content><p>Ray 乐忠于旅游，这次他来到了T 城。T 城是一个水上城市，一共有 N 个景点，有些景点之间会用一座桥连接。为了方便游客到达每个景点但又为了节约成本，T 城的任意两个景点之间有且只有一条路径。换句话说， T 城中只有N − 1 座桥。Ray 发现，有些桥上可以看到美丽的景色，让人心情愉悦，但有些桥狭窄泥泞，令人烦躁。于是，他给每座桥定义一个愉悦度w，也就是说，Ray 经过这座桥会增加w 的愉悦度，这或许是正的也可能是负的。有时，Ray 看待同一座桥的心情也会发生改变。现在，Ray 想让你帮他计算从u 景点到v 景点能获得的总愉悦度。有时，他还想知道某段路上最美丽的桥所提供的最大愉悦度，或是某段路上最糟糕的一座桥提供的最低愉悦度。</p></div><h2>Input</h2><div class=content><p>输入的第一行包含一个整数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。</p></div><h2>Output</h2><div class=content><p>对于每一个询问(操作S、MAX 和MIN)，输出答案。</p></div><h2>Sample Input</h2>
<div class=content><span class=sampledata>2000<br />
0 1 -332<br />
0 2 202<br />
1 3 -103<br />
3 4 -438<br />
1 5 821<br />
0 6 -859<br />
1 7 -992<br />
5 8 -200<br />
5 9 653<br />
0 10 874<br />
0 11 -639<br />
3 12 -537<br />
2 13 -271<br />
4 14 952<br />
2 15 620<br />
4 16 667<br />
9 17 -345<br />
14 18 176<br />
11 19 -868<br />
14 20 -525<br />
5 21 -42<br />
11 22 -176<br />
8 23 -335<br />
14 24 -120<br />
9 25 -192<br />
3 26 -718<br />
26 27 -692<br />
6 28 781<br />
21 29 523<br />
17 30 344<br />
11 31 136<br />
22 32 -14<br />
20 33 879<br />
0 34 -101<br />
14 35 13<br />
18 36 78<br />
29 37 -339<br />
26 38 -64<br />
35 39 -803<br />
1 40 201<br />
4 41 683<br />
3 42 289<br />
18 43 787<br />
42 44 -415<br />
25 45 -199<br />
45 46 566<br />
25 47 -504<br />
31 48 -159<br />
19 49 -730<br />
40 50 501<br />
39 51 -772<br />
19 52 254<br />
12 53 152<br />
20 54 773<br />
18 55 -323<br />
36 56 911<br />
45 57 -986<br />
3 58 465<br />
17 59 -732<br />
29 60 -777<br />
41 61 92<br />
34 62 -881<br />
15 63 -660<br />
60 64 78<br />
60 65 -743<br />
57 66 450<br />
37 67 -730<br />
0 68 -512<br />
54 69 565<br />
68 70 885<br />
26 71 -208<br />
5 72 272<br />
3 73 -448<br />
30 74 -837<br />
68 75 900<br />
49 76 4<br />
19 77 -825<br />
0 78 695<br />
19 79 198<br />
49 80 -761<br />
76 81 -536<br />
57 82 54<br />
2 83 507<br />
46 84 271<br />
27 85 360<br />
18 86 -574<br />
45 87 -50<br />
52 88 -486<br />
38 89 992<br />
11 90 880<br />
52 91 -379<br />
54 92 554<br />
36 93 120<br />
83 94 -575<br />
70 95 577<br />
71 96 329<br />
86 97 467<br />
68 98 890<br />
8 99 482<br />
3 100 601<br />
45 101 872<br />
16 102 -893<br />
33 103 -161<br />
86 104 438<br />
30 105 -587<br />
22 106 835<br />
88 107 314<br />
2 108 -56<br />
101 109 -807<br />
17 110 -249<br />
6 111 147<br />
32 112 -75<br />
51 113 -981<br />
77 114 144<br />
71 115 88<br />
90 116 457<br />
38 117 886<br />
1 118 339<br />
27 119 -144<br />
109 120 -332<br />
72 121 651<br />
110 122 417<br />
73 123 5<br />
6 124 -45<br />
39 125 -157<br />
119 126 -917<br />
126 127 -99<br />
120 128 718<br />
6 129 -63<br />
17 130 536<br />
107 131 162<br />
64 132 -16<br />
42 133 227<br />
132 134 -115<br />
129 135 -787<br />
68 136 -91<br />
66 137 170<br />
7 138 -616<br />
75 139 801<br />
18 140 -513<br />
54 141 -840<br />
15 142 305<br />
111 143 -307<br />
97 144 538<br />
137 145 883<br />
25 146 211<br />
43 147 179<br />
10 148 -237<br />
76 149 632<br />
1 150 -955<br />
50 151 -685<br />
13 152 -178<br />
118 153 -607<br />
65 154 -227<br />
74 155 -897<br />
96 156 509<br />
12 157 388<br />
154 158 -119<br />
98 159 835<br />
19 160 710<br />
156 161 -837<br />
2 162 875<br />
53 163 -770<br />
153 164 -138<br />
89 165 843<br />
160 166 -179<br />
136 167 -25<br />
157 168 -244<br />
46 169 -594<br />
107 170 -324<br />
136 171 -654<br />
164 172 444<br />
89 173 -446<br />
127 174 372<br />
163 175 858<br />
29 176 662<br />
34 177 117<br />
170 178 -524<br />
63 179 288<br />
3 180 -678<br />
31 181 802<br />
97 182 -599<br />
18 183 901<br />
139 184 259<br />
12 185 357<br />
9 186 488<br />
120 187 676<br />
156 188 -5<br />
160 189 -187<br />
40 190 -826<br />
52 191 -438<br />
53 192 -753<br />
180 193 -515<br />
42 194 -418<br />
150 195 619<br />
65 196 -984<br />
14 197 -281<br />
128 198 311<br />
192 199 -755<br />
64 200 -960<br />
68 201 -940<br />
61 202 -137<br />
110 203 -985<br />
84 204 79<br />
19 205 338<br />
87 206 55<br />
31 207 -798<br />
10 208 136<br />
9 209 140<br />
41 210 575<br />
19 211 295<br />
194 212 735<br />
43 213 -320<br />
207 214 748<br />
180 215 171<br />
215 216 -473<br />
80 217 -128<br />
213 218 -920<br />
191 219 -639<br />
96 220 273<br />
138 221 526<br />
24 222 157<br />
217 223 -699<br />
106 224 973<br />
126 225 125<br />
10 226 756<br />
161 227 -749<br />
1 228 991<br />
159 229 650<br />
38 230 414<br />
175 231 82<br />
177 232 609<br />
65 233 -555<br />
161 234 955<br />
68 235 963<br />
7 236 -495<br />
157 237 -774<br />
51 238 216<br />
102 239 512<br />
7 240 525<br />
100 241 406<br />
51 242 -387<br />
198 243 -674<br />
240 244 703<br />
133 245 898<br />
118 246 -647<br />
160 247 -387<br />
9 248 -511<br />
102 249 -236<br />
107 250 865<br />
5 251 -215<br />
55 252 772<br />
38 253 146<br />
165 254 95<br />
127 255 289<br />
199 256 -593<br />
110 257 456<br />
238 258 465<br />
200 259 -263<br />
16 260 315<br />
181 261 -718<br />
136 262 170<br />
245 263 -257<br />
232 264 511<br />
1 265 217<br />
129 266 -767<br />
2 267 -584<br />
138 268 -874<br />
207 269 -895<br />
122 270 333<br />
178 271 397<br />
174 272 645<br />
173 273 875<br />
251 274 -810<br />
233 275 834<br />
46 276 246<br />
130 277 844<br />
36 278 -875<br />
50 279 189<br />
273 280 -907<br />
173 281 -875<br />
229 282 521<br />
16 283 445<br />
24 284 660<br />
254 285 982<br />
105 286 -500<br />
147 287 -711<br />
176 288 787<br />
171 289 -633<br />
229 290 -669<br />
198 291 -847<br />
108 292 874<br />
12 293 107<br />
28 294 -860<br />
261 295 192<br />
233 296 -300<br />
209 297 674<br />
241 298 416<br />
110 299 -19<br
bzoj problem （2000个子文件） 
2157.html 92KB 2548.html 73KB 2550.html 66KB 2470.html 39KB 1868.html 34KB 2518.html 33KB 3117.html 30KB 2624.html 29KB 2760.html 26KB 3567.html 26KB 2290.html 25KB 2427.html 25KB 2690.html 23KB 2484.html 22KB 2783.html 21KB 3633.html 20KB 2544.html 19KB 2553.html 19KB 2321.html 19KB 2706.html 18KB 2386.html 18KB 3670.html 17KB 3757.html 17KB 2993.html 16KB 2905.html 16KB 3116.html 16KB 2804.html 16KB 3469.html 16KB 2267.html 16KB 2543.html 16KB 2598.html 15KB 2667.html 15KB 4013.html 15KB 2245.html 15KB 2731.html 15KB 2546.html 15KB 2178.html 15KB 2767.html 15KB 2243.html 14KB 4343.html 14KB 2762.html 13KB 4020.html 13KB 3482.html 13KB 2547.html 13KB 2744.html 12KB 3568.html 12KB 2459.html 12KB 2285.html 12KB 4088.html 12KB 3818.html 12KB 3827.html 12KB 2278.html 12KB 2540.html 12KB 3220.html 12KB 2522.html 12KB 2016.html 12KB 1722.html 11KB 2269.html 11KB 3669.html 11KB 2730.html 11KB 2770.html 11KB 3271.html 11KB 2503.html 11KB 2246.html 11KB 2864.html 11KB 4066.html 10KB 2691.html 10KB 2623.html 10KB 2322.html 10KB 2268.html 10KB 3342.html 10KB 2666.html 10KB 2300.html 10KB 1361.html 10KB 2528.html 10KB 2707.html 10KB 2283.html 10KB 2833.html 10KB 2683.html 9KB 3226.html 9KB 3152.html 9KB 1972.html 9KB 2865.html 9KB 3217.html 9KB 1033.html 9KB 2325.html 9KB 4364.html 9KB 2603.html 9KB 2446.html 9KB 2574.html 9KB 2313.html 9KB 2809.html 8KB 2805.html 8KB 4021.html 8KB 2273.html 8KB 2284.html 8KB 3630.html 8KB 2265.html 8KB 3828.html 8KB 2813.html 8KB共 2000 条
- 1
- 2
- 3
- 4
- 5
- 6
- 20
资源评论
