已經發現數據有問題

第3個測試點
第1行是511 500
然而後面有512 499(請自行用Ctrl+F搜尋,一共出現了3次)
請在讀入時

x=((x<1)?1:x);
x=((x>n)?n:x);
y=((y<1)?1:y);
y=((y>n)?n:y);

完整AC代碼

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

long long n,m,cnt,ans;
long long R=1;
long long fa[10000+1];
long long e_x[10000+1];
long long e_y[10000+1];
long long e_d[10000+1];
long long dep[10000+1];
long long dis[10000+1];
long long vis[10000+1];
long long rec_f[10000+1];
vector<long long> rec_p;
vector<long long> rec_d;
vector<long long> st_rec_d_l;
vector<long long> st_rec_d_r;
vector<long long> st_rec_d_mid;
vector<long long> st_rec_d_min;
vector<long long> st_rec_d_min_p;
vector<vector<long long> > e;
vector<vector<long long> > d;
deque<long long> q;

void pr_q_1()
{
    q.clear();
    for (long long i=1;i<n;i++)
        q.push_back(i);
}

void pr_tree_1()
{
    e.clear();
    e.resize(n+1);
    d.clear();
    d.resize(n+1);
    memset(dep,0,sizeof(dep));
    dep[R]=0;
    memset(dis,0,sizeof(dis));
    dis[R]=0;
    memset(vis,0,sizeof(vis));
    vis[R]=1;
    memset(fa,0,sizeof(fa));
    for (pr_q_1();!q.empty();q.pop_front())
    {
        long long now=q.front();
        if (vis[e_x[now]]==1||vis[e_y[now]]==1)
        {
            if (vis[e_y[now]]==1)
                swap(e_x[now],e_y[now]);
            vis[e_y[now]]=1;
            dep[e_y[now]]=dep[e_x[now]]+1;
            dis[e_y[now]]=dis[e_x[now]]+e_d[now];
            fa[e_y[now]]=e_x[now];
            e[e_x[now]].push_back(e_y[now]);
            d[e_x[now]].push_back(e_d[now]);
        }
        else
            q.push_back(now);
    }
}

void update_rec_1(long long now)
{
    rec_p.push_back(now);
    rec_d.push_back(dep[now]);
    if (rec_f[now]==0)
        rec_f[now]=rec_p.size()-1;
}

void dfs_tree_2(long long now);

void dfs_tree_1(long long now)
{
    rec_p.clear();
    rec_p.resize(1,0);
    rec_d.clear();
    rec_d.resize(1,0);
    memset(rec_f,0,sizeof(rec_f));
    update_rec_1(now);
    dfs_tree_2(now);
}

void dfs_tree_2(long long now)
{
    for (long long i=0;i<e[now].size();i++)
    {
        update_rec_1(e[now][i]);
        dfs_tree_2(e[now][i]);
    }
    if (now!=R)
        update_rec_1(fa[now]);
}

void build_st_rec_d_2(long long now,long long l,long long r);

void build_st_rec_d_1(long long now,long long l,long long r)
{
    long long size=(long long)((1<<int(ceil(log2(r-l+1))+1))+2);
    st_rec_d_l.clear();
    st_rec_d_l.resize(size);
    st_rec_d_r.clear();
    st_rec_d_r.resize(size);
    st_rec_d_mid.clear();
    st_rec_d_mid.resize(size);
    st_rec_d_min.clear();
    st_rec_d_min.resize(size);
    st_rec_d_min_p.clear();
    st_rec_d_min_p.resize(size);
    build_st_rec_d_2(now,l,r);
}

void build_st_rec_d_2(long long now,long long l,long long r)
{
    st_rec_d_l[now]=l;
    st_rec_d_r[now]=r;
    st_rec_d_mid[now]=(l+r)/2;
    if (l==r)
    {
        st_rec_d_min[now]=rec_d[l];
        st_rec_d_min_p[now]=l;
    }
    else if (l<r)
    {
        if (l<=st_rec_d_mid[now])
            build_st_rec_d_2(now*2,l,st_rec_d_mid[now]);
        if (st_rec_d_mid[now]+1<=r)
            build_st_rec_d_2(now*2+1,st_rec_d_mid[now]+1,r);
        if (st_rec_d_min[now*2]<=st_rec_d_min[now*2+1])
        {
            st_rec_d_min[now]=st_rec_d_min[now*2];
            st_rec_d_min_p[now]=st_rec_d_min_p[now*2];
        }
        else
        {
            st_rec_d_min[now]=st_rec_d_min[now*2+1];
            st_rec_d_min_p[now]=st_rec_d_min_p[now*2+1];
        }
    }
}

long long sum_st_rec_d_min_1(long long now,long long l,long long r)
{
    if (st_rec_d_l[now]==l&&r==st_rec_d_r[now])
        return st_rec_d_min[now];
    else if (r<=st_rec_d_mid[now])
        return sum_st_rec_d_min_1(now*2,l,r);
    else if (st_rec_d_mid[now]+1<=l)
        return sum_st_rec_d_min_1(now*2+1,l,r);
    else
        return min(sum_st_rec_d_min_1(now*2,l,st_rec_d_mid[now]),sum_st_rec_d_min_1(now*2+1,st_rec_d_mid[now]+1,r));
}

long long sum_st_rec_d_min_p_1(long long now,long long l,long long r)
{
    if (st_rec_d_l[now]==l&&r==st_rec_d_r[now])
        return st_rec_d_min_p[now];
    else if (r<=st_rec_d_mid[now])
        return sum_st_rec_d_min_p_1(now*2,l,r);
    else if (st_rec_d_mid[now]+1<=l)
        return sum_st_rec_d_min_p_1(now*2+1,l,r);
    else
    {
        if (sum_st_rec_d_min_1(now*2,l,st_rec_d_mid[now])<=sum_st_rec_d_min_1(now*2+1,st_rec_d_mid[now]+1,r))
            return sum_st_rec_d_min_p_1(now*2,l,st_rec_d_mid[now]);
        else
            return sum_st_rec_d_min_p_1(now*2+1,st_rec_d_mid[now]+1,r);
    }
}

void pr_lca_1()
{
    pr_tree_1();
    dfs_tree_1(R);
    build_st_rec_d_1(1,1,rec_d.size()-1);
}

long long lca_1(long long x,long long y)
{
    return rec_p[sum_st_rec_d_min_p_1(1,min(rec_f[x],rec_f[y]),max(rec_f[x],rec_f[y]))];
}

int main()
{
    while (~scanf("%lld%lld",&n,&m))
    {
        for (long long i=1;i<n;i++)
            scanf("%lld%lld%lld",&e_x[i],&e_y[i],&e_d[i]);
        pr_lca_1();
        cnt=ans=0;
        for (long long i=1;i<=m;i++)
        {
            long long x,y;
            scanf("%lld%lld",&x,&y);
            //測試數據好像有問題,處理錯誤
            x=((x<1)?1:x);
            x=((x>n)?n:x);
            y=((y<1)?1:y);
            y=((y>n)?n:y);
            //測試數據好像有問題,處理錯誤
            if (lca_1(x,y)==x)
            {
                cnt++;
                ans+=abs(dis[x]-dis[y]);
            }
        }
        printf("%lld\n",cnt);
        printf("%lld\n",ans);
    }
}

第3個測試點完整數據
輸入
511 500
1 511 7
1 510 4
510 509 5
510 508 6
508 507 1
508 506 9
506 505 8
506 504 10
504 503 7
504 502 5
502 501 6
502 500 9
500 499 8
500 498 4
498 497 10
498 496 3
496 495 3
496 494 7
494 493 10
494 492 9
492 491 1
492 490 9
490 489 6
490 488 8
488 487 5
488 486 10
486 485 9
486 484 3
484 483 2
484 482 7
482 481 8
482 480 3
480 479 8
480 478 4
478 477 6
478 476 6
476 475 7
476 474 9
474 473 8
474 472 7
472 471 1
472 470 10
470 469 4
470 468 1
468 467 1
468 466 9
466 465 8
466 464 1
464 463 4
464 462 10
462 461 3
462 460 10
460 459 3
460 458 6
458 457 9
458 456 3
456 455 3
456 454 10
454 453 1
454 452 8
452 451 3
452 450 9
450 449 9
450 448 3
448 447 5
448 446 8
446 445 5
446 444 9
444 443 6
444 442 9
442 441 1
442 440 3
440 439 8
440 438 3
438 437 3
438 436 6
436 435 9
436 434 2
434 433 1
434 432 3
432 431 10
432 430 8
430 429 2
430 428 7
428 427 7
428 426 10
426 425 5
426 424 2
424 423 5
424 422 4
422 421 1
422 420 7
420 419 3
420 418 3
418 417 9
418 416 10
416 415 6
416 414 3
414 413 3
414 412 2
412 411 7
412 410 10
410 409 7
410 408 4
408 407 5
408 406 3
406 405 4
406 404 9
404 403 9
404 402 5
402 401 4
402 400 3
400 399 6
400 398 7
398 397 1
398 396 9
396 395 1
396 394 2
394 393 3
394 392 5
392 391 8
392 390 9
390 389 7
390 388 2
388 387 2
388 386 10
386 385 6
386 384 8
384 383 8
384 382 10
382 381 1
382 380 4
380 379 6
380 378 10
378 377 3
378 376 2
376 375 1
376 374 8
374 373 7
374 372 10
372 371 10
372 370 6
370 369 7
370 368 7
368 367 3
368 366 10
366 365 7
366 364 4
364 363 1
364 362 1
362 361 2
362 360 5
360 359 7
360 358 7
358 357 9
358 356 4
356 355 8
356 354 2
354 353 10
354 352 10
352 351 4
352 350 9
350 349 7
350 348 3
348 347 6
348 346 1
346 345 5
346 344 8
344 343 3
344 342 6
342 341 4
342 340 8
340 339 7
340 338 9
338 337 9
338 336 4
336 335 2
336 334 8
334 333 9
334 332 6
332 331 8
332 330 9
330 329 7
330 328 7
328 327 8
328 326 4
326 325 10
326 324 3
324 323 2
324 322 2
322 321 6
322 320 2
320 319 9
320 318 5
318 317 5
318 316 4
316 315 9
316 314 6
314 313 5
314 312 3
312 311 1
312 310 2
310 309 9
310 308 4
308 307 7
308 306 10
306 305 1
306 304 8
304 303 2
304 302 7
302 301 10
302 300 7
300 299 7
300 298 8
298 297 1
298 296 8
296 295 4
296 294 6
294 293 7
294 292 4
292 291 3
292 290 5
290 289 6
290 288 3
288 287 7
288 286 10
286 285 9
286 284 9
284 283 2
284 282 7
282 281 7
282 280 7
280 279 4
280 278 8
278 277 2
278 276 2
276 275 7
276 274 7
274 273 4
274 272 7
272 271 9
272 270 6
270 269 5
270 268 6
268 267 10
268 266 7
266 265 9
266 264 6
264 263 1
264 262 10
262 261 9
262 260 4
260 259 3
260 258 9
258 257 10
258 256 3
256 255 3
256 254 4
254 253 3
254 252 3
252 251 8
252 250 6
250 249 5
250 248 1
248 247 8
248 246 6
246 245 2
246 244 8
244 243 2
244 242 7
242 241 8
242 240 7
240 239 5
240 238 1
238 237 7
238 236 7
236 235 4
236 234 3
234 233 10
234 232 7
232 231 8
232 230 7
230 229 2
230 228 10
228 227 10
228 226 6
226 225 7
226 224 1
224 223 2
224 222 6
222 221 3
222 220 1
220 219 8
220 218 8
218 217 2
218 216 4
216 215 5
216 214 10
214 213 4
214 212 6
212 211 2
212 210 3
210 209 3
210 208 7
208 207 8
208 206 7
206 205 4
206 204 5
204 203 1
204 202 6
202 201 3
202 200 10
200 199 5
200 198 7
198 197 3
198 196 6
196 195 4
196 194 10
194 193 5
194 192 8
192 191 1
192 190 3
190 189 7
190 188 1
188 187 10
188 186 1
186 185 4
186 184 8
184 183 5
184 182 8
182 181 8
182 180 1
180 179 3
180 178 5
178 177 10
178 176 7
176 175 6
176 174 8
174 173 4
174 172 8
172 171 2
172 170 1
170 169 7
170 168 3
168 167 3
168 166 4
166 165 1
166 164 2
164 163 6
164 162 9
162 161 9
162 160 10
160 159 4
160 158 1
158 157 1
158 156 5
156 155 4
156 154 6
154 153 6
154 152 9
152 151 8
152 150 10
150 149 4
150 148 10
148 147 4
148 146 6
146 145 6
146 144 1
144 143 5
144 142 8
142 141 10
142 140 8
140 139 5
140 138 4
138 137 1
138 136 5
136 135 10
136 134 4
134 133 10
134 132 6
132 131 8
132 130 2
130 129 5
130 128 6
128 127 3
128 126 1
126 125 7
126 124 1
124 123 10
124 122 3
122 121 9
122 120 5
120 119 9
120 118 5
118 117 7
118 116 2
116 115 3
116 114 9
114 113 2
114 112 8
112 111 5
112 110 9
110 109 9
110 108 1
108 107 9
108 106 6
106 105 10
106 104 7
104 103 3
104 102 6
102 101 8
102 100 1
100 99 6
100 98 4
98 97 2
98 96 4
96 95 9
96 94 10
94 93 9
94 92 4
92 91 8
92 90 7
90 89 10
90 88 3
88 87 10
88 86 7
86 85 5
86 84 5
84 83 4
84 82 9
82 81 5
82 80 6
80 79 10
80 78 8
78 77 5
78 76 8
76 75 1
76 74 2
74 73 3
74 72 9
72 71 6
72 70 3
70 69 1
70 68 8
68 67 4
68 66 5
66 65 2
66 64 5
64 63 5
64 62 7
62 61 10
62 60 5
60 59 1
60 58 2
58 57 2
58 56 8
56 55 1
56 54 9
54 53 9
54 52 7
52 51 10
52 50 3
50 49 10
50 48 6
48 47 6
48 46 6
46 45 8
46 44 8
44 43 3
44 42 9
42 41 10
42 40 2
40 39 5
40 38 7
38 37 10
38 36 10
36 35 1
36 34 10
34 33 2
34 32 3
32 31 8
32 30 6
30 29 2
30 28 9
28 27 6
28 26 1
26 25 8
26 24 1
24 23 4
24 22 2
22 21 6
22 20 3
20 19 5
20 18 8
18 17 7
18 16 3
16 15 7
16 14 6
14 13 8
14 12 9
12 11 6
12 10 7
10 9 2
10 8 5
8 7 9
8 6 2
6 5 1
6 4 8
4 3 2
4 2 2
132 119
494 481
356 343
180 167
228 215
490 477
156 143
512 499
260 247
468 455
280 267
198 185
398 385
164 151
378 365
234 221
162 149
512 499
196 183
141 327
280 267
252 239
370 357
214 201
422 409
412 399
214 201
228 215
310 297
212 199
316 303
398 385
376 363
182 169
264 251
462 449
296 283
506 493
244 231
153 292
470 457
230 217
190 177
238 225
130 117
354 341
298 285
490 477
206 193
162 149
470 457
416 403
124 111
360 347
456 443
352 339
120 107
170 157
308 295
44 352
280 267
160 147
208 195
236 223
124 111
394 381
360 347
304 291
380 367
338 325
444 431
342 329
328 315
412 399
350 337
404 391
246 233
288 275
474 461
4 230
390 377
424 411
410 397
384 371
370 357
466 453
370 357
158 145
300 287
334 321
292 279
166 153
152 139
402 389
216 203
310 297
194 181
182 169
340 327
136 381
236 223
470 457
404 391
478 465
134 121
116 103
268 255
136 123
392 379
346 333
368 355
276 263
406 393
246 233
176 163
426 413
344 331
228 215
126 113
87 220
354 341
230 217
414 401
454 441
190 177
502 489
498 485
148 135
496 483
260 247
370 357
368 355
392 379
114 101
430 417
148 135
364 351
316 303
134 121
37 250
310 297
418 405
152 139
432 419
306 293
116 103
424 411
186 173
298 285
168 155
168 155
374 361
122 109
268 255
338 325
350 337
234 221
378 365
128 115
15 464
250 237
458 445
128 115
452 439
446 433
374 361
372 359
492 479
252 239
304 291
356 343
254 241
244 231
352 339
374 361
272 259
402 389
444 431
226 213
87 468
458 445
452 439
384 371
242 229
426 413
346 333
290 277
268 255
134 121
316 303
236 223
506 493
314 301
188 175
304 291
198 185
292 279
368 355
346 333
139 416
260 247
344 331
344 331
474 461
490 477
118 105
340 327
460 447
332 319
318 305
184 171
330 317
344 331
342 329
268 255
258 245
310 297
218 205
146 133
120 231
458 445
234 221
288 275
448 435
346 333
134 121
400 387
142 129
238 225
300 287
134 121
148 135
402 389
258 245
486 473
146 133
242 229
512 499
344 331
32 370
240 227
154 141
348 335
326 313
198 185
240 227
134 121
208 195
348 335
198 185
120 107
390 377
510 497
282 269
462 449
304 291
286 273
460 447
208 195
133 323
180 167
310 297
386 373
372 359
116 103
284 271
264 251
424 411
292 279
178 165
256 243
330 317
292 279
374 361
358 345
406 393
144 131
362 349
282 269
94 308
114 101
244 231
156 143
474 461
388 375
292 279
404 391
414 401
128 115
472 459
146 133
238 225
474 461
198 185
338 325
442 429
154 141
228 215
502 489
139 476
156 143
126 113
474 461
424 411
414 401
444 431
184 171
188 175
338 325
166 153
240 227
180 167
492 479
460 447
422 409
448 435
322 309
486 473
396 383
41 213
460 447
226 213
168 155
148 135
160 147
202 189
458 445
436 423
470 457
302 289
142 129
242 229
340 327
354 341
178 165
136 123
432 419
116 103
206 193
27 385
308 295
136 123
410 397
232 219
504 491
330 317
196 183
126 113
496 483
336 323
468 455
300 287
322 309
132 119
120 107
120 107
346 333
164 151
212 199
61 467
484 471
388 375
494 481
240 227
264 251
192 179
484 471
400 387
406 393
296 283
350 337
382 369
338 325
310 297
134 121
124 111
274 261
300 287
460 447
40 472
252 239
442 429
340 327
138 125
180 167
438 425
454 441
390 377
200 187
466 453
268 255
468 455
200 187
314 301
246 233
224 211
496 483
470 457
310 297
171 214
410 397
166 153
508 495
254 241
496 483
214 201
504 491
170 157
462 449
172 159
398 385
372 359
440 427
402 389
232 219
190 177
326 313
258 245
390 377
62 475
458 445
122 109
494 481
120 107
144 131
222 209
450 437
176 163
250 237
454 441
432 419
162 149
266 253
286 273
206 193
162 149
436 423
510 497
306 293
17 429
502 489
428 415
350 337
312 299
176 163
288 275
210 197
398 385
186 173
156 143
452 439
196 183
326 313
170 157
232 219
376 363
176 163
396 383
404 391
42 216
464 451
204 191
210 197
320 307
138 125
434 421
496 483
294 281
326 313
470 457
386 373
240 227
176 163
326 313
354 341
138 125
172 159
432 419
506 493
165 435
418 405
296 283
484 471
322 309
218 205
366 353
246 233
500 487
374 361
266 253
492 479
314 301
286 273
256 243
182 169
294 281
432 419
204 191
362 349
189 461
輸出
472
19272

0 条评论

目前还没有评论...

信息

ID
1460
难度
7
分类
树结构 | 最近公共祖先 点击显示
标签
递交数
1779
已通过
347
通过率
20%
被复制
9
上传者