#2322. 大森林

    ID: 2322 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>PROV赛事:contest30来源:qoj.ac数据:公开样例最短路径线段树树状数组

大森林

大森林

题目描述

NOI2016 浙江省队选拔赛第二试 大森林 大森林 【问题描述】 小Y 家里有一个大森林,里面有 𝑛 棵树,编号从 1 到 𝑛 。一开始这些树都 只是树苗,只有一个节点,标号为 1 。这些树都有一个特殊的节点,我们称之为 生长节点,这些节点有生长出子节点的能力。 小Y 掌握了一种魔法,能让第 𝑙 棵树到第 𝑟 棵树的生长节点长出一个子节点。 同时她还能修改第 𝑙 棵树到第 𝑟 棵树的生长节点。 她告诉了你她使用魔法的记录,你能不能管理她家的森林,并且回答她的询 问呢? 【输入格式】 输入文件forest.in 第一行包含 2 个正整数 𝑛, 𝑚,共有 𝑛 棵树和 𝑚 个操作。 接下来 𝑚 行,每行包含若干非负整数表示一个操作,操作格式为: 1. 0 𝑙 𝑟 表示将第 𝑙 棵树到第 𝑟 棵树的生长节点下面长出一个子节点, 子节点的标号为上一个 0 号操作叶子标号加 1(例如,第一个 0 号 操作产生的子节点标号为 2), 𝑙 到 𝑟 之间的树长出的节点标号都相 同。保证 1 ≤𝑙≤𝑟≤𝑛 。 2. 1 𝑙 𝑟 𝑥 表示将第 𝑙 棵树到第 𝑟 棵树的生长节点改到标号为 𝑥 的节点。 对于 𝑖 (𝑙≤𝑖≤𝑟) 这棵树,如果标号 𝑥 的点不在其中,那么这个操 作对该树不产生影响。保证 1 ≤𝑙≤𝑟≤𝑛 , 𝑥 不超过当前所有树中 节点最大的标号。 3. 2 𝑥 𝑢 𝑣 询问第 𝑥 棵树中节点 𝑢 到节点 𝑣 点的距离,也就是在第 𝑥 棵 树中从节点 𝑢 和节点 𝑣 的最短路上边的数量。保证1 ≤𝑥≤𝑛,这棵 树中节点 𝑢 和节点 𝑣 存在。 【输出格式】 输出文件为forest.out。 输出包括若干行,按顺序对于每个小Y 的询问输出答案。 【样例输入1】 5 5 0 1 5 1 2 4 2

NOI2016 浙江省队选拔赛第二试 大森林 0 1 4 2 1 1 3 2 2 1 3 【样例输出1】 1 2 【样例输入输出2】 见选手目录下的forest/forest.in 与forest/forest.ans。 【数据规模和约定】 各测试点满足以下约定: 测试点 𝑛 𝑚 约定 1 ≤103 ≤103 无 2 ≤105 ≤2 × 105 保证每次 0 和 1 操作修改的是 1 到 𝑛 所有的树 3 4 保证每次 0 操作生长节点都是 这些树中编号最大的节点 5 6 无 7 8 9 10

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 5
0 1 5
1 2 4 2
0 1 4
2 1 1 3
2 2 1 3
1
2

样例 2

1000 1000
0 76 759
0 278 782
0 36 551
0 510 738
2 360 4 3
2 513 4 4
2 949 1 1
2 449 3 1
0 432 784
2 980 1 1
2 322 2 3
0 250 910
1 45 640 3
1 285 322 4
0 431 997
2 711 1 1
0 576 971
2 639 7 3
0 178 317
0 322 809
2 494 4 8
0 269 634
2 363 2 7
2 273 10 4
0 260 885
1 465 476 9
0 68 260
1 361 628 8
1 5 674 14
1 348 603 1
0 343 535
1 645 979 14
2 97 4 14
0 39 161
0 748 807
0 811 938
1 22 575 9
0 128 408
0 551 669
1 204 216 20
2 51 4 4
1 444 860 4
2 206 4 1
0 84 150
2 848 7 7
2 155 1 16
2 420 13 3
1 247 607 18
0 735 738
2 818 18 13
1 179 533 9
1 373 863 16
1 262 460 2
0 92 705
1 574 741 11
0 216 464
0 216 474
2 940 9 9
1 223 876 22
1 304 837 12
2 56 4 4
0 509 840
1 514 656 24
0 271 418
1 230 990 7
1 388 694 6
2 810 13 1
1 139 995 9
0 505 917
1 133 959 24
2 420 4 12
2 652 8 7
1 182 812 8
2 915 8 28
2 852 9 9
2 82 2 1
2 263 10 19
1 99 215 26
1 124 453 3
2 625 1 12
2 650 3 1
1 420 548 12
0 27 249
2 226 24 10
2 204 4 19
0 501 930
1 237 983 9
2 217 2 23
0 783 845
2 101 2 16
1 243 563 29
0 150 766
2 682 11 26
0 745 921
0 407 887
0 258 611
0 609 889
1 231 844 23
2 452 35 34
1 259 610 17
1 614 845 2
2 104 21 1
0 61 259
2 598 28 23
1 98 308 20
0 561 633
0 67 127
1 256 665 31
1 373 730 37
1 205 810 24
2 903 18 7
1 171 819 26
2 48 29 16
2 46 16 16
1 805 918 24
1 145 789 35
0 229 254
2 615 2 8
2 610 6 20
0 589 939
2 142 29 23
1 361 396 6
2 978 1 1
0 181 237
1 657 995 18
1 465 655 37
1 958 996 19
1 623 922 10
2 309 13 3
1 202 464 40
1 503 563 18
0 570 886
2 82 2 2
0 169 419
2 144 14 19
2 585 7 12
2 441 6 15
2 591 34 13
1 670 910 40
2 575 1 34
0 652 880
1 309 532 35
2 597 26 13
0 504 619
2 23 1 1
2 601 35 6
0 754 947
0 149 677
1 283 553 48
2 390 13 7
2 655 11 5
2 510 26 46
0 269 759
1 615 990 35
0 215 694
0 333 798
1 350 778 12
1 422 732 34
0 708 962
1 172 847 13
0 212 304
0 542 844
1 129 184 34
0 534 836
0 327 792
2 898 28 7
0 238 976
1 370 889 45
0 919 983
1 140 938 57
2 54 29 16
2 706 11 28
0 15 266
1 193 311 19
2 944 52 8
0 5 850
0 893 992
0 843 938
1 187 673 50
1 537 740 27
1 744 888 13
0 84 422
0 91 836
0 47 410
1 61 952 18
0 971 985
2 653 55 28
1 375 627 43
0 143 505
0 373 439
1 714 826 11
0 279 741
0 45 268
0 950 994
0 65 343
2 121 23 2
0 118 249
1 243 424 32
0 712 741
2 748 60 43
1 693 844 45
1 450 540 67
0 507 889
1 219 872 52
1 262 859 39
2 108 59 1
1 500 698 75
0 95 270
2 986 1 71
1 518 875 72
2 521 49 6
0 458 808
0 14 725
1 464 647 65
0 485 882
0 477 572
2 337 69 78
1 13 271 70
1 405 560 79
2 409 27 2
2 524 48 69
0 145 632
2 63 29 70
2 352 3 64
2 525 48 75
1 296 939 12
2 533 69 48
1 22 448 81
0 345 752
2 942 9 61
0 254 894
2 340 69 4
0 386 504
2 637 82 77
2 524 69 7
1 765 789 27
0 158 381
1 205 933 47
2 41 16 1
2 80 16 2
2 984 1 1
2 621 5 1
2 337 60 69
1 44 865 36
1 740 743 78
0 388 900
0 51 528
0 637 676
2 143 21 19
2 140 64 21
0 149 573
2 217 23 63
0 363 762
1 162 542 9
1 565 999 1
0 233 975
1 300 601 10
1 455 652 14
2 845 28 31
1 16 799 80
2 883 62 18
0 104 513
2 314 91 92
1 30 902 31
1 36 404 68
1 464 639 18
0 25 284
1 364 826 38
2 831 75 18
0 515 754
0 37 607
0 885 979
1 744 751 84
2 2 1 1
2 722 49 56
1 151 697 30
0 74 641
1 290 515 16
0 671 832
1 481 905 95
2 713 30 83
0 84 128
2 702 51 26
0 287 998
1 828 834 6
0 145 183
0 391 738
1 179 267 29
0 310 478
1 261 397 16
0 17 480
0 88 667
0 202 383
2 762 77 100
0 514 798
1 109 706 94
2 242 23 53
0 209 650
1 88 418 2
0 187 280
0 197 689
1 234 234 46
0 338 620
0 559 942
1 499 646 98
1 46 652 84
2 104 39 63
2 645 77 83
1 580 955 75
0 451 664
2 546 82 80
1 318 454 26
2 325 81 63
1 403 944 66
2 893 96 62
1 19 529 18
1 282 528 107
1 2 820 109
2 345 3 69
2 313 1 69
2 10 60 1
0 388 716
1 322 897 29
0 369 436
0 188 689
0 107 414
2 301 72 117
1 186 860 72
1 798 948 90
1 343 514 36
0 848 886
2 169 63 14
0 273 464
2 527 108 80
1 687 771 101
2 641 54 41
2 438 6 87
0 66 289
1 96 770 12
2 126 105 60
2 963 96 61
1 522 582 100
1 235 995 86
2 866 41 28
2 425 50 35
1 480 742 29
1 268 595 59
2 294 60 1
0 258 425
1 144 657 110
0 643 741
0 339 405
1 126 950 49
1 308 373 58
1 457 907 25
0 526 566
0 293 682
0 327 746
1 203 979 18
2 431 110 13
0 365 593
0 204 800
0 372 685
2 875 36 28
1 53 623 111
1 430 996 74
0 64 903
1 571 622 106
0 194 516
2 166 64 60
0 62 245
2 287 19 120
2 468 7 67
0 322 398
0 580 695
0 178 679
0 79 278
0 828 976
2 661 82 8
1 681 994 131
1 176 791 24
1 110 684 84
1 271 560 46
0 106 428
0 518 545
2 832 60 43
2 676 48 11
2 909 9 28
0 195 644
2 483 130 80
0 344 391
0 164 904
0 351 430
2 142 132 37
1 156 350 96
1 232 323 94
1 374 539 128
2 474 78 11
0 344 548
1 508 589 9
1 631 924 67
2 933 18 112
2 36 29 78
2 969 91 8
2 856 8 130
2 426 12 82
2 10 1 60
0 16 756
1 499 918 125
0 124 414
1 241 241 31
1 156 392 16
0 504 819
2 286 85 142
1 244 764 20
1 446 517 20
1 44 769 127
2 352 57 106
0 273 410
2 762 33 86
0 201 537
1 828 876 25
2 45 1 145
1 98 721 100
1 120 557 29
2 108 97 95
0 572 768
0 366 982
1 100 186 40
1 64 611 145
0 688 807
2 13 1 60
0 230 889
1 114 988 100
1 657 814 53
1 249 378 35
1 4 878 60
1 58 308 97
2 909 137 7
0 658 666
1 499 620 18
2 458 64 84
1 495 893 145
2 436 51 108
2 766 17 26
2 502 56 81
1 858 941 2
1 72 174 83
0 254 791
2 426 49 64
1 329 907 142
1 142 270 107
2 24 59 78
1 202 317 99
1 220 395 55
0 180 771
0 115 498
2 266 138 25
2 664 2 107
1 667 698 82
2 548 13 147
2 283 1 27
1 405 864 119
0 287 421
0 365 620
2 393 105 102
0 168 988
1 568 682 2
0 483 987
0 880 970
2 1 1 1
1 264 757 52
1 231 707 20
0 701 973
2 266 106 109
0 80 100
1 435 883 161
1 171 947 107
1 15 652 81
0 245 947
0 6 326
1 323 576 55
0 524 879
2 47 60 166
0 642 731
1 77 758 115
2 956 71 151
0 165 424
1 188 490 161
0 383 932
1 28 292 166
0 408 782
2 3 1 1
1 575 695 114
0 156 924
1 212 805 153
1 566 706 163
2 925 161 9
2 679 7 23
1 102 836 36
1 350 743 2
1 632 755 48
0 392 900
0 155 952
0 424 675
1 344 421 14
1 106 973 85
1 289 625 60
2 871 163 86
2 77 16 59
0 269 367
2 853 151 47
0 629 886
1 195 676 122
0 443 753
1 565 832 64
1 395 923 27
2 308 3 27
1 245 794 127
2 602 125 161
1 195 857 38
1 244 373 147
1 116 939 48
1 95 814 141
1 404 433 148
2 428 175 153
1 190 466 74
0 314 749
0 242 951
0 597 624
0 293 673
1 107 256 21
2 177 174 60
0 626 1000
0 140 809
1 114 911 182
2 189 67 65
1 232 354 157
2 365 15 64
2 192 166 105
1 717 878 43
2 382 32 11
2 615 155 30
0 23 760
1 597 617 160
0 267 671
0 669 741
0 555 964
0 292 632
1 256 362 90
1 190 504 182
1 121 164 105
2 720 155 155
2 222 104 106
0 473 489
2 107 97 120
0 602 673
2 669 91 45
1 165 811 152
1 240 576 15
1 27 481 160
0 525 578
1 66 696 102
1 146 996 66
0 50 244
2 846 188 41
2 149 185 23
2 957 9 183
2 504 83 6
2 92 37 95
2 882 79 165
0 20 88
2 63 65 65
0 249 418
1 229 306 62
0 431 679
2 462 32 35
1 15 906 65
0 459 938
2 294 165 89
0 225 781
0 506 972
1 606 996 62
2 951 188 96
1 432 541 127
0 212 818
0 542 559
2 783 30 28
1 338 505 70
1 452 538 85
2 893 165 197
0 193 409
0 470 756
1 65 333 124
0 67 690
0 613 724
1 437 715 85
1 52 70 12
1 718 815 8
2 945 161 188
2 604 165 75
2 673 41 28
2 937 18 162
0 103 920
1 538 627 35
1 443 622 66
1 247 911 199
2 554 196 198
2 538 35 55
0 463 627
1 28 337 87
2 806 130 41
2 497 64 200
0 350 801
2 149 72 204
2 640 160 41
2 588 79 198
1 705 775 48
1 418 458 86
0 661 997
1 564 842 117
1 136 629 41
1 321 498 27
2 911 28 9
0 421 513
0 55 108
2 702 107 102
1 131 620 178
2 10 1 1
0 156 673
2 862 180 43
2 24 185 166
0 114 888
2 39 1 29
1 18 481 154
2 934 163 62
1 61 606 26
0 17 741
0 41 753
1 34 487 191
2 753 32 1
2 437 1 182
2 886 33 86
0 485 615
1 118 254 98
1 262 943 185
1 703 817 197
2 395 123 138
2 647 48 60
1 608 917 119
2 273 4 214
1 169 912 73
1 10 158 34
2 567 3 147
2 458 91 206
2 595 3 35
1 177 994 8
0 687 699
1 8 266 34
1 286 906 11
2 413 153 142
0 842 968
0 237 851
1 634 952 83
0 734 977
1 274 645 71
1 395 429 102
1 13 915 43
2 379 69 160
1 102 184 191
2 132 185 130
0 370 550
0 240 650
2 635 2 161
1 510 670 10
2 951 174 180
2 488 213 110
0 379 394
0 76 450
0 198 996
1 190 494 28
1 490 598 90
2 794 199 200
1 553 714 63
0 31 114
1 805 930 208
2 595 174 140
2 194 146 136
0 140 462
1 76 550 14
0 58 830
1 464 707 31
2 71 166 60
1 889 918 95
0 334 452
1 199 342 12
2 247 78 14
1 88 803 70
1 574 585 136
0 210 835
2 195 95 120
0 54 515
0 568 923
1 214 302 50
1 201 943 140
2 636 20 2
1 844 881 209
1 46 815 146
1 138 385 68
1 405 962 36
2 106 60 138
0 693 744
0 378 692
2 211 116 59
0 436 570
2 297 219 108
1 297 884 69
1 412 658 166
2 590 186 46
2 410 225 172
1 63 163 26
0 623 912
0 490 976
1 82 213 110
2 462 104 91
2 886 112 160
1 553 997 145
0 262 674
1 28 111 219
1 410 451 138
2 401 27 169
1 454 639 2
1 450 929 213
2 418 35 78
1 271 750 14
0 350 806
2 51 194 193
2 207 117 146
0 628 978
0 301 817
2 62 228 95
2 246 157 166
0 400 408
1 262 379 241
2 943 237 9
2 383 143 1
0 96 501
0 425 559
1 649 668 89
0 421 623
1 49 954 171
2 692 6 153
0 486 687
1 261 464 43
0 187 455
0 135 756
2 874 240 52
2 203 42 231
1 180 235 93
0 437 467
0 42 477
1 446 837 167
0 363 675
2 689 51 3
1 576 835 239
1 268 370 87
0 704 911
0 48 641
2 687 60 219
0 102 368
2 754 43 208
2 316 57 138
0 805 918
1 411 707 176
0 384 930
1 567 810 219
2 176 87 215
0 200 562
1 773 973 77
1 327 432 61
0 329 633
0 260 863
2 568 80 130
1 495 897 32
0 194 697
2 697 107 8
1 290 916 253
0 132 166
1 570 889 35
2 397 65 86
0 151 959
0 144 992
2 983 58 225
2 601 3 35
2 95 1 65
2 977 160 160
1 6 570 259
2 977 1 100
0 18 830
2 98 72 78
0 652 974
2 45 93 70
0 124 917
0 153 766
0 160 388
0 779 791
0 164 368
1 270 349 108
1 736 776 30
2 283 105 2
0 559 797
2 306 87 130
2 81 104 166
2 432 186 153
0 181 917
1 451 475 78
0 182 910
1 853 901 66
1 38 879 256
1 310 636 192
0 125 604
1 524 691 57
2 374 104 179
0 316 653
1 289 951 96
0 286 731
1 668 817 45
2 655 273 91
2 499 258 237
2 993 71 225
1 78 869 104
1 325 554 248
0 649 676
1 608 824 2
2 643 184 50
2 936 188 265
2 24 194 194
2 765 75 208
1 151 716 107
0 171 253
1 315 581 18
0 88 980
0 928 967
0 166 187
0 728 985
0 65 905
1 315 338 267
0 499 515
0 168 759
2 157 32 279
1 139 413 72
1 31 279 262
0 549 553
0 240 372
0 187 570
2 371 260 111
2 872 273 57
2 35 185 59
0 652 982
2 797 55 151
1 492 787 63
2 464 249 102
0 81 707
0 299 970
0 71 474
1 900 996 72
1 93 326 161
1 18 805 167
2 576 75 111
2 671 122 241
2 394 239 263
1 642 645 132
1 225 784 59
2 769 271 283
0 137 692
2 314 230 259
2 98 29 105
0 364 772
1 256 914 195
2 363 131 12
2 496 15 86
2 207 89 92
2 747 163 79
0 208 816
2 378 82 131
2 225 42 42
1 699 917 282
1 550 748 237
0 36 800
1 328 926 174
1 584 738 106
2 644 5 188
0 112 987
1 756 795 48
2 622 182 50
2 160 2 228
1 536 737 140
0 608 836
1 150 881 139
1 484 917 44
0 481 557
1 326 579 11
2 175 268 293
2 728 160 130
1 65 465 171
0 387 547
1 73 299 231
2 979 100 1
0 242 721
1 517 675 19
1 302 352 53
1 310 586 209
1 464 981 153
1 296 524 200
0 234 800
1 863 1000 194
2 899 220 112
0 130 295
2 234 63 120
0 8 581
0 693 973
1 219 636 199
0 388 895
0 287 448
1 570 830 84
2 4 1 1
0 561 857
2 610 160 94
1 96 510 260
2 915 305 151
1 5 116 268
0 391 457
0 567 741
1 179 863 285
0 183 395
2 575 171 238
2 734 197 203
2 519 113 199
1 29 997 251
1 13 292 14
0 410 675
2 551 196 262
0 612 613
0 510 932
0 266 266
2 792 314 240
1 34 357 17
1 511 539 10
0 679 980
0 405 617
0 466 593
1 437 632 121
2 856 259 137
1 136 182 221
2 751 91 107
2 796 1 306
0 185 950
0 33 714
2 391 185 140
1 276 720 260
1 658 682 299
0 631 788
1 207 960 266
2 751 45 283
0 451 589
1 230 731 22
0 139 758
2 883 255 319
2 803 184 273
0 145 154
0 43 945
0 448 515
0 102 212
2 282 57 295
2 394 86 100
2 814 163 33
1 504 567 75
0 256 508
2 939 161 289
0 235 986
2 542 300 142
1 438 880 311
0 333 576
1 264 709 248
1 418 768 222
1 386 811 305
0 337 877
1 377 436 119
1 155 397 295
2 595 172 113
2 123 297 130
2 792 259 272
0 189 548
0 319 871
0 13 591
1 551 763 67
2 796 36 41
0 218 426
1 760 861 235
1 588 642 201
2
0
0
1
0
2
0
2
3
2
2
2
0
1
0
2
1
2
0
0
1
3
2
3
0
1
2
2
1
3
3
3
3
1
2
2
4
2
2
0
3
4
2
0
3
0
1
3
2
3
3
3
0
4
3
2
3
3
2
3
3
4
3
5
2
1
6
6
4
2
2
4
2
2
1
6
2
7
1
3
0
1
7
2
2
4
2
2
7
2
0
5
6
1
4
4
2
2
6
6
4
4
5
1
7
1
2
5
8
3
3
2
2
3
7
2
2
8
7
6
5
2
1
3
4
7
2
2
2
3
5
1
7
5
3
2
2
1
3
5
4
2
9
3
2
3
4
7
2
2
0
7
1
3
0
3
2
4
2
2
4
7
10
5
2
6
5
2
9
0
2
5
4
5
3
3
4
3
4
0
2
2
3
4
2
2
2
5
3
2
4
6
5
3
4
11
1
2
0
4
2
1
5
2
5
5
8
6
7
5
7
2
10
9
5
1
2
13
2
7
2
1
4
5
3
4
5
5
4
5
2
4
7
3
2
4
3
3
3
3
5
5
4
4
5
5
6
1
11
2
7
3
2
2
0
1
2
1
5
7
3
6
10
4
7
3
3
4
0
9
5
9
5
4
6
8
9
10
3
6
8
3
5
4
2
2
7
0
6
3
3
3
3
1
3
3
0
3
5
10
2
5
14
6
5
2
5
4
4
7
7
8
8
5
4
6
3
6
2
4