fork(3) download
  1. {$M 4000000000}
  2. const maxn = 1000;
  3. fi = '';
  4. fo = '';
  5. oo = 1000000000;
  6. type node = record
  7. num: word;
  8. x: array[1..maxn] of word;
  9. c: array[1..maxn] of word;
  10. end;
  11. var n,q: word;
  12. a: array[1..maxn] of node;
  13. procedure enter;
  14. var i,u,v,cap:word;
  15. begin
  16. assign(input,fi);
  17. reset(input);
  18. readln(n,q);
  19. for i:=1 to n-1 do
  20. begin
  21. readln(u,v,cap);
  22. with a[u] do
  23. begin
  24. inc(num);
  25. x[num]:=v;
  26. c[num]:=cap;
  27. end;
  28. with a[v] do
  29. begin
  30. inc(num);
  31. x[num]:=u;
  32. c[num]:=cap;
  33. end;
  34. end;
  35. end;
  36.  
  37. procedure solve;
  38. var i,u,v:word;
  39. len: longint;
  40. visit: array[1..maxn] of boolean;
  41. procedure dfs(i:word);
  42. var j:word;
  43. begin
  44. visit[i]:=true;
  45. if i=v then writeln(len)
  46. else
  47. with a[i] do
  48. for j:=1 to num do
  49. if not (visit[x[j]]) then
  50. begin
  51. len:=len+c[j];
  52. dfs(x[j]);
  53. len:=len-c[j];
  54. end;
  55. end;
  56. begin
  57. assign(output,fo);
  58. rewrite(output);
  59. for i:=1 to q do
  60. begin
  61. fillchar(visit,sizeof(visit),false);
  62. readln(u,v);
  63. len:=0;
  64. dfs(u);
  65. end;
  66. close(output);
  67. close(input);
  68. end;
  69. begin
  70. enter;
  71. solve;
  72. end.
  73.  
Success #stdin #stdout 0s 4184KB
stdin
1000 1
712 1 7015
901 2 4272
124 3 6948
225 4 9036
104 5 3213
228 6 4513
449 7 2773
251 8 4123
474 9 9908
315 10 9337
83 11 2861
697 12 2211
494 13 7948
372 14 198
832 15 1363
143 16 2369
15 17 9682
138 18 1634
345 19 1476
907 20 4899
83 21 8048
106 22 8757
903 23 2881
607 24 7926
317 25 2731
850 26 4861
445 27 3372
859 28 981
565 29 4303
768 30 2071
705 31 625
472 32 4934
662 33 6940
986 34 2217
862 35 7471
25 36 1399
316 37 5825
978 38 5436
945 39 5280
275 40 3176
407 41 1996
774 42 6449
164 43 1934
332 44 406
812 45 8973
563 46 2299
578 47 7109
920 48 3001
302 49 3038
180 50 4903
80 51 5684
925 52 9005
852 53 7597
540 54 3919
670 55 7943
608 56 6441
307 57 9820
482 58 492
988 59 3985
451 60 872
618 61 1337
891 62 7817
723 63 4182
884 64 8419
34 65 5163
48 66 3606
944 67 7685
111 68 9793
466 69 4539
524 70 978
835 71 8115
387 72 8923
709 73 4800
328 74 3877
286 75 2647
376 76 5005
701 77 1886
104 78 1224
670 79 7252
387 80 5893
568 81 6499
90 82 4985
208 83 6205
553 84 3620
90 85 7198
856 86 771
553 87 418
188 88 3216
735 89 4994
639 90 1522
892 91 6109
80 92 4566
225 93 8625
400 94 7573
788 95 2775
104 96 1232
603 97 140
970 98 2902
613 99 4884
487 100 5812
106 101 1276
604 102 9618
467 103 6243
322 104 1153
952 105 6017
877 106 7539
951 107 6891
565 108 4744
298 109 186
322 110 3198
894 111 3225
579 112 741
466 113 2938
578 114 3809
206 115 8838
336 116 2462
515 117 7202
245 118 2557
180 119 2540
813 120 4258
723 121 114
630 122 1121
335 123 3807
653 124 9826
466 125 3895
727 126 1297
920 127 8509
433 128 5271
111 129 737
175 130 6609
900 131 4985
903 132 4277
824 133 213
350 134 2362
581 135 4461
852 136 8459
27 137 7198
478 138 4316
44 139 1356
48 140 1065
884 141 6983
213 142 3052
445 143 2019
937 144 8028
801 145 7832
450 146 2879
138 147 1975
661 148 608
119 149 8253
144 150 1312
637 151 3218
473 152 1015
253 153 9145
768 154 5284
649 155 9621
992 156 1450
560 157 4364
622 158 1565
774 159 6686
338 160 4623
646 161 3495
470 162 4750
133 163 4332
317 164 7772
986 165 3162
701 166 6157
188 167 1880
555 168 5538
514 169 2727
723 170 4319
856 171 7465
577 172 2764
512 173 4422
381 174 750
149 175 9969
810 176 4980
245 177 242
809 178 1720
320 179 9392
701 181 2859
621 182 7969
602 183 5319
457 184 8828
245 185 5810
29 186 7154
333 187 4070
340 188 9717
100 189 7728
759 190 8150
315 191 7484
387 192 6877
951 193 7155
240 194 2431
959 195 2377
898 196 3278
903 197 4443
197 198 4070
975 199 2534
604 200 8553
993 201 3876
800 202 1508
529 203 1691
582 204 9809
194 205 9607
611 206 9143
119 207 4985
754 208 7577
701 209 3999
250 210 1899
650 211 8320
623 212 4403
344 213 2882
618 214 1068
727 215 6740
889 216 6858
651 217 3773
65 218 1434
137 219 5019
887 220 6871
828 221 5275
997 222 4509
953 223 7606
968 224 1011
652 225 1004
96 226 1290
986 227 3792
10 228 5989
628 229 277
474 230 8783
40 231 4035
413 232 7211
901 233 435
272 234 4145
62 235 1733
731 236 1828
47 237 8738
712 238 7069
72 239 690
838 240 304
24 241 9325
209 242 4144
430 243 5934
703 244 5877
261 245 6244
523 246 5179
170 247 2123
948 248 8190
481 249 2822
637 250 253
587 251 4175
966 252 6769
658 253 4620
124 254 2081
495 255 9080
554 256 7591
61 257 2210
765 258 8137
701 259 6547
36 260 7284
478 261 6915
603 262 6277
505 263 1403
164 264 7218
983 265 4201
832 266 2271
799 267 9210
51 268 425
893 269 4157
374 270 764
909 271 7712
474 272 8107
972 273 5152
779 274 4022
137 275 6949
945 276 9621
502 277 3192
790 278 7129
800 279 399
882 280 2041
776 281 1696
595 282 1639
399 283 4138
883 284 3178
820 285 1972
322 286 6228
705 287 394
455 288 7163
733 289 5300
662 290 5313
93 291 1423
320 292 3559
357 293 9167
290 294 9713
969 295 6267
766 296 4328
338 297 4874
662 298 5718
402 299 3304
338 300 4984
649 301 6225
378 302 3202
100 303 5592
877 304 9181
334 305 3577
879 306 7399
849 307 3881
738 308 5018
585 309 7014
87 310 8019
523 311 5773
169 312 2264
415 313 7778
290 314 3084
845 315 5451
11 316 5798
104 317 9878
339 318 5924
950 319 4043
983 320 3173
472 321 9220
180 322 8679
701 323 9692
495 324 1612
65 325 9031
255 326 3887
103 327 3729
24 328 7734
146 329 188
27 330 7341
667 331 7648
756 332 1100
417 333 9504
119 334 3366
578 335 1079
534 336 1842
754 337 1793
821 338 6253
48 339 5203
948 340 3435
701 341 7277
326 342 2531
464 343 7923
763 344 1869
888 345 1282
608 346 7544
141 347 1031
430 348 9484
652 349 2912
393 350 9294
117 351 1317
51 352 1330
702 353 1663
24 354 7449
842 355 8135
399 356 5017
534 357 3338
42 358 8281
298 359 7116
967 360 179
833 361 634
912 362 867
658 363 7279
151 364 1900
776 365 1997
845 366 2604
128 367 4959
820 368 1327
794 369 2307
452 370 5263
130 371 8762
5 372 1990
553 373 626
832 374 6006
363 375 1675
199 376 7214
565 377 6937
209 378 7195
683 379 3719
544 380 5790
15 381 6662
695 382 3627
445 383 3785
201 384 4853
231 385 1551
481 386 4265
286 387 5752
771 388 168
572 389 8345
777 390 521
175 391 1925
988 392 4089
497 393 9006
230 394 6040
978 395 7722
930 396 5882
207 397 2310
57 398 84
966 399 6338
211 400 2548
943 401 3308
164 402 6779
682 403 2815
402 404 2568
769 405 8839
745 406 4260
415 407 309
652 408 352
932 409 7227
714 410 1180
693 411 4168
496 412 6740
56 413 9114
14 414 8295
110 415 3186
521 416 5531
888 417 1667
575 418 1500
574 419 1580
524 420 5264
878 421 2032
841 422 9930
939 423 8468
552 424 4202
580 425 1019
658 426 5585
755 427 385
887 428 4564
858 429 9913
474 430 1339
292 431 8133
372 432 2046
188 433 2042
637 434 3793
340 435 7529
554 436 985
880 437 4870
51 438 2549
567 439 60
866 440 8842
927 441 1417
744 442 9813
983 443 2746
793 444 9035
180 445 4693
256 446 3639
982 447 7810
666 448 7044
110 449 8211
652 450 562
471 451 8645
167 452 7787
438 453 1954
667 454 2746
383 455 5933
77 456 5292
451 457 6449
601 458 2518
279 459 367
730 460 4269
488 461 3695
395 462 3286
344 463 8981
662 464 2081
209 465 3871
65 466 7998
946 467 9046
748 468 5654
362 469 102
754 470 7474
104 471 8641
800 472 421
733 473 602
104 474 1037
300 475 3719
547 476 5299
308 477 1733
471 478 3973
191 479 7766
471 480 9361
112 481 5141
778 482 4769
879 483 205
983 484 2420
275 485 4561
1 486 5631
901 487 2387
894 488 3791
629 489 5345
225 490 154
533 491 117
576 492 6130
402 493 6538
66 494 6856
701 495 2834
443 496 7085
315 497 5628
104 498 4378
68 499 9155
563 500 6148
857 501 6795
982 502 9975
189 503 3748
64 504 2493
216 505 9638
325 506 3620
100 507 6987
874 508 3220
813 509 4693
904 510 2174
391 511 4088
857 512 2969
796 513 9811
984 514 5582
757 515 311
502 516 3779
579 517 4736
710 518 9089
836 519 6599
789 520 8389
708 521 519
345 522 2724
530 523 7850
470 524 9024
138 525 876
128 526 4074
238 527 7619
415 528 7590
24 529 6547
487 530 4596
340 531 9812
733 532 4988
820 533 3491
554 534 2867
975 535 6094
255 536 3499
384 537 1743
143 538 9069
545 539 193
526 540 7587
89 541 2202
362 542 4717
231 543 6265
158 544 4364
930 545 1710
455 546 4801
729 547 3704
464 548 9502
191 549 9241
253 550 6593
637 551 7782
888 552 7949
840 553 3385
387 554 8540
251 555 1385
623 556 3164
52 557 6733
304 558 3966
245 559 1753
172 560 3767
348 561 4355
450 562 8067
15 563 5261
5 564 6691
146 565 1213
425 566 4410
562 567 7843
824 568 611
311 569 1791
202 570 6281
464 571 9669
275 572 2853
432 573 1529
186 574 4710
27 575 8983
58 576 5977
430 577 1422
562 578 358
137 579 8292
533 580 3495
372 581 2437
800 582 7439
600 583 5373
652 584 3433
615 585 939
765 586 5691
335 587 6221
472 588 8549
79 589 2399
334 590 3270
387 591 9161
869 592 9885
28 593 1938
70 594 8898
554 595 2340
406 596 2750
260 597 7626
667 598 2857
52 599 2725
953 600 5757
884 601 9457
927 602 6642
571 603 6771
847 604 7658
433 605 9257
455 606 6684
901 607 9024
934 608 3380
272 609 2242
860 610 2500
953 611 5778
727 612 1013
714 613 4602
1 614 8067
857 615 3645
723 616 5797
429 617 5013
715 618 622
253 619 5727
786 620 5797
946 621 7373
15 622 7305
78 623 2136
475 624 6319
435 625 6870
703 626 8215
545 627 9455
434 628 6551
912 629 4839
978 630 874
731 631 8956
253 632 6227
785 633 6256
591 634 3150
915 635 6995
68 636 5491
769 637 6906
104 638 4699
111 639 9305
127 640 5690
397 641 2763
567 642 4296
9 643 4721
286 644 886
472 645 6832
840 646 3355
563 647 6574
938 648 8460
417 649 5420
947 650 6806
445 651 4117
901 652 4731
986 653 4492
581 654 2021
753 655 1525
164 656 7688
683 657 384
112 658 5735
567 659 1807
406 660 1095
901 661 9611
856 662 10000
415 663 5466
799 664 8225
524 665 9032
845 666 2646
286 667 1400
173 668 4250
763 669 6227
685 670 5078
432 671 8611
845 672 6866
223 673 2443
551 674 7285
428 675 2098
763 676 356
378 677 7873
684 678 1529
985 679 7483
576 680 799
549 681 1341
582 682 4904
361 683 2011
482 684 2426
104 685 586
850 686 4919
608 687 9146
518 688 6634
685 689 6093
336 690 5932
198 691 7996
805 692 6722
130 693 2700
60 694 7291
149 695 9764
825 696 4340
290 697 4242
688 698 6343
125 699 2375
454 700 3997
471 701 8331
223 702 5925
452 703 6759
765 704 8006
464 705 1214
870 706 7176
332 707 1352
957 708 6858
915 709 8359
567 710 5563
908 711 7719
845 712 2465
714 713 2880
482 714 9577
5 715 8246
234 716 1547
877 717 8906
352 718 1140
966 719 8552
148 720 8474
203 721 8914
435 722 8543
34 723 817
720 724 9232
888 725 4700
778 726 7368
18 727 9377
13 728 4541
992 729 6101
409 730 9121
159 731 144
851 732 3412
119 733 945
457 734 8140
195 735 8677
2 736 7272
493 737 4462
75 738 4491
84 739 2074
945 740 2595
554 741 5006
913 742 3531
947 743 9166
164 744 5945
533 745 3686
915 746 3316
207 747 9439
348 748 5323
124 749 9396
472 750 9432
843 751 4710
510 752 8216
701 753 7432
982 754 4412
519 755 6395
986 756 1110
51 757 9244
849 758 4104
88 759 9772
120 760 3723
703 761 7041
578 762 4835
137 763 9112
348 764 7456
629 765 9432
664 766 84
352 767 8704
15 768 4112
575 769 361
340 770 4772
423 771 2046
378 772 2522
887 773 5581
712 774 6936
224 775 4812
580 776 5355
408 777 5693
824 778 3505
461 779 2947
786 780 9055
647 781 1163
268 782 1563
794 783 3590
93 784 7332
452 785 1804
15 786 2194
308 787 8293
925 788 3432
799 789 6902
425 790 8329
195 791 4205
962 792 8306
352 793 7308
786 794 9655
533 795 4117
786 796 6521
223 797 3330
553 798 4689
611 799 3776
591 800 6840
753 801 8632
952 802 6461
11 803 5722
800 804 8869
985 805 5595
446 806 8881
251 807 1619
851 808 7886
575 809 5402
170 810 4149
514 811 9982
144 812 2811
833 813 8675
137 814 2666
553 815 7558
393 816 8303
449 817 2244
18 818 7662
983 819 5992
180 820 837
629 821 4297
582 822 4388
571 823 9216
234 824 9262
322 825 5912
470 826 1451
509 827 3813
533 828 149
765 829 3769
231 830 9547
537 831 3861
180 832 9181
578 833 3126
988 834 897
738 835 2018
849 836 4161
239 837 1350
859 838 41
770 839 7220
601 840 6326
125 841 6573
828 842 2264
397 843 6410
666 844 295
149 845 6547
339 846 6430
376 847 2412
555 848 8659
184 849 768
644 850 7118
376 851 8277
948 852 1586
302 853 3927
315 854 4311
845 855 9865
554 856 6806
915 857 7448
939 858 2551
457 859 3553
858 860 2195
563 861 3990
332 862 3215
124 863 334
181 864 7854
198 865 8955
763 866 5826
632 867 2951
901 868 6228
731 869 5335
396 870 4237
348 871 6517
230 872 7838
318 873 3032
967 874 2874
322 875 1162
291 876 2522
715 877 4909
701 878 4360
580 879 4890
461 880 1212
524 881 9598
917 882 4134
630 883 1402
833 884 5261
864 885 4461
95 886 9874
816 887 4999
207 888 2329
487 889 4235
523 890 5052
853 891 7048
945 892 4760
498 893 857
930 894 8869
740 895 5294
86 896 2491
671 897 9864
425 898 2946
308 899 8894
856 900 7494
286 901 8219
517 902 4272
708 903 5074
18 904 6060
844 905 5005
144 906 3083
677 907 4743
685 908 5495
438 909 7218
167 910 9695
814 911 4845
814 912 8825
89 913 9254
525 914 3900
1 915 440
385 916 8820
220 917 880
576 918 9725
605 919 3537
5 920 3848
668 921 2900
645 922 5110
820 923 6208
420 924 2718
575 925 178
65 926 3838
770 927 6627
753 928 3600
646 929 7996
137 930 4751
264 931 3198
25 932 7472
154 933 9768
383 934 9022
277 935 2721
232 936 8621
845 937 336
146 938 4918
579 939 4235
505 940 4882
392 941 4636
573 942 1591
279 943 8930
796 944 3102
652 945 5356
104 946 6454
862 947 3043
533 948 6839
330 949 3515
946 950 2622
180 951 8489
49 952 8665
149 953 1023
455 954 7594
391 955 1942
31 956 8444
106 957 4659
851 958 2531
884 959 7298
599 960 1517
607 961 7985
501 962 7730
824 963 2577
101 964 4627
396 965 7920
251 966 8684
652 967 5102
717 968 8509
646 969 5117
111 970 4557
109 971 272
317 972 9703
238 973 1106
855 974 8593
666 975 786
910 976 8309
659 977 2552
24 978 3990
571 979 7513
940 980 9527
802 981 528
317 982 4211
450 983 1647
368 984 9372
335 985 7245
286 986 7746
10 987 2494
946 988 1924
381 989 4407
549 990 5501
549 991 5193
786 992 3247
256 993 4418
76 994 7226
109 995 2403
242 996 3006
821 997 8379
454 998 7870
274 999 483
271 1000 9471
1 1000
stdout
86006