从一根柱子上开始的:

$n=100,m=1\dots 500$

1   : 3
2   : 8
3   : 17
4   : 28
5   : 43
6   : 62
7   : 89
8   : 118
9   : 151
10  : 188
11  : 233
12  : 282
13  : 339
14  : 404
15  : 485
16  : 568
17  : 655
18  : 746
19  : 845
20  : 948
21  : 1059
22  : 1178
23  : 1313
24  : 1452
25  : 1599
26  : 1754
27  : 1925
28  : 2104
29  : 2299
30  : 2510
31  : 2753
32  : 2998
33  : 3247
34  : 3500
35  : 3761
36  : 4026
37  : 4299
38  : 4580
39  : 4877
40  : 5178
41  : 5487
42  : 5804
43  : 6137
44  : 6478
45  : 6835
46  : 7208
47  : 7613
48  : 8022
49  : 8439
50  : 8864
51  : 9305
52  : 9754
53  : 10219
54  : 10700
55  : 11213
56  : 11734
57  : 12271
58  : 12824
59  : 13409
60  : 14010
61  : 14643
62  : 15308
63  : 16037
64  : 16768
65  : 17503
66  : 18242
67  : 18989
68  : 19740
69  : 20499
70  : 21266
71  : 22049
72  : 22836
73  : 23631
74  : 24434
75  : 25253
76  : 26080
77  : 26923
78  : 27782
79  : 28673
80  : 29568
81  : 30471
82  : 31382
83  : 32309
84  : 33244
85  : 34195
86  : 35162
87  : 36161
88  : 37168
89  : 38191
90  : 39230
91  : 40301
92  : 41388
93  : 42507
94  : 43658
95  : 44873
96  : 46092
97  : 47319
98  : 48554
99  : 49805
100 : 51064
101 : 52339
102 : 53630
103 : 54953
104 : 56284
105 : 57631
106 : 58994
107 : 60389
108 : 61800
109 : 63243
110 : 64718
111 : 66257
112 : 67804
113 : 69367
114 : 70946
115 : 72557
116 : 74184
117 : 75843
118 : 77534
119 : 79289
120 : 81060
121 : 82863
122 : 84698
123 : 86597
124 : 88528
125 : 90523
126 : 92582
127 : 94769
128 : 96958
129 : 99151
130 : 101348
131 : 103553
132 : 105762
133 : 107979
134 : 110204
135 : 112445
136 : 114690
137 : 116943
138 : 119204
139 : 121481
140 : 123766
141 : 126067
142 : 128384
143 : 130733
144 : 133086
145 : 135447
146 : 137816
147 : 140201
148 : 142594
149 : 145003
150 : 147428
151 : 149885
152 : 152350
153 : 154831
154 : 157328
155 : 159857
156 : 162402
157 : 164979
158 : 167588
159 : 170261
160 : 172938
161 : 175623
162 : 178316
163 : 181025
164 : 183742
165 : 186475
166 : 189224
167 : 192005
168 : 194794
169 : 197599
170 : 200420
171 : 203273
172 : 206142
173 : 209043
174 : 211976
175 : 214973
176 : 217978
177 : 220999
178 : 224036
179 : 227105
180 : 230190
181 : 233307
182 : 236456
183 : 239669
184 : 242898
185 : 246159
186 : 249452
187 : 252809
188 : 256198
189 : 259651
190 : 263168
191 : 266813
192 : 270462
193 : 274119
194 : 277784
195 : 281465
196 : 285154
197 : 288859
198 : 292580
199 : 296333
200 : 300094
201 : 303871
202 : 307664
203 : 311489
204 : 315330
205 : 319203
206 : 323108
207 : 327077
208 : 331054
209 : 335047
210 : 339056
211 : 343097
212 : 347154
213 : 351243
214 : 355364
215 : 359549
216 : 363750
217 : 367983
218 : 372248
219 : 376577
220 : 380938
221 : 385363
222 : 389852
223 : 394469
224 : 399094
225 : 403735
226 : 408392
227 : 413081
228 : 417786
229 : 422523
230 : 427292
231 : 432125
232 : 436974
233 : 441855
234 : 446768
235 : 451745
236 : 456754
237 : 461827
238 : 466964
239 : 472229
240 : 477510
241 : 482823
242 : 488168
243 : 493577
244 : 499018
245 : 504523
246 : 510092
247 : 515789
248 : 521518
249 : 527311
250 : 533168
251 : 539153
252 : 545202
253 : 551379
254 : 557684
255 : 564245
256 : 570808
257 : 577375
258 : 583946
259 : 590525
260 : 597108
261 : 603699
262 : 610298
263 : 616913
264 : 623532
265 : 630159
266 : 636794
267 : 643445
268 : 650104
269 : 656779
270 : 663470
271 : 670193
272 : 676920
273 : 683655
274 : 690398
275 : 697157
276 : 703924
277 : 710707
278 : 717506
279 : 724337
280 : 731176
281 : 738031
282 : 744902
283 : 751805
284 : 758724
285 : 765675
286 : 772658
287 : 779705
288 : 786756
289 : 793815
290 : 800882
291 : 807965
292 : 815056
293 : 822163
294 : 829286
295 : 836441
296 : 843604
297 : 850783
298 : 857978
299 : 865205
300 : 872448
301 : 879723
302 : 887030
303 : 894401
304 : 901780
305 : 909175
306 : 916586
307 : 924029
308 : 931488
309 : 938979
310 : 946502
311 : 954089
312 : 961692
313 : 969327
314 : 976994
315 : 984725
316 : 992488
317 : 1000315
318 : 1008206
319 : 1016225
320 : 1024248
321 : 1032279
322 : 1040318
323 : 1048373
324 : 1056436
325 : 1064515
326 : 1072610
327 : 1080737
328 : 1088872
329 : 1097023
330 : 1105190
331 : 1113389
332 : 1121604
333 : 1129851
334 : 1138130
335 : 1146473
336 : 1154824
337 : 1163191
338 : 1171574
339 : 1179989
340 : 1188420
341 : 1196883
342 : 1205378
343 : 1213937
344 : 1222512
345 : 1231119
346 : 1239758
347 : 1248461
348 : 1257196
349 : 1265995
350 : 1274858
351 : 1283849
352 : 1292848
353 : 1301863
354 : 1310894
355 : 1319957
356 : 1329036
357 : 1338147
358 : 1347290
359 : 1356497
360 : 1365720
361 : 1374975
362 : 1384262
363 : 1393613
364 : 1402996
365 : 1412443
366 : 1421954
367 : 1431593
368 : 1441248
369 : 1450935
370 : 1460654
371 : 1470437
372 : 1480252
373 : 1490131
374 : 1500074
375 : 1510145
376 : 1520248
377 : 1530415
378 : 1540646
379 : 1551005
380 : 1561428
381 : 1571979
382 : 1582658
383 : 1593593
384 : 1604532
385 : 1615479
386 : 1626434
387 : 1637405
388 : 1648384
389 : 1659379
390 : 1670390
391 : 1681433
392 : 1692484
393 : 1703551
394 : 1714634
395 : 1725749
396 : 1736880
397 : 1748043
398 : 1759238
399 : 1770497
400 : 1781764
401 : 1793047
402 : 1804346
403 : 1815677
404 : 1827024
405 : 1838403
406 : 1849814
407 : 1861289
408 : 1872780
409 : 1884303
410 : 1895858
411 : 1907477
412 : 1919128
413 : 1930843
414 : 1942622
415 : 1954529
416 : 1966444
417 : 1978375
418 : 1990322
419 : 2002301
420 : 2014296
421 : 2026323
422 : 2038382
423 : 2050505
424 : 2062644
425 : 2074815
426 : 2087018
427 : 2099285
428 : 2111584
429 : 2123947
430 : 2136374
431 : 2148929
432 : 2161500
433 : 2174103
434 : 2186738
435 : 2199437
436 : 2212168
437 : 2224963
438 : 2237822
439 : 2250809
440 : 2263828
441 : 2276911
442 : 2290058
443 : 2303333
444 : 2316672
445 : 2330139
446 : 2343734
447 : 2357585
448 : 2371444
449 : 2385319
450 : 2399210
451 : 2413133
452 : 2427072
453 : 2441043
454 : 2455046
455 : 2469113
456 : 2483196
457 : 2497311
458 : 2511458
459 : 2525669
460 : 2539912
461 : 2554219
462 : 2568590
463 : 2583089
464 : 2597604
465 : 2612151
466 : 2626730
467 : 2641373
468 : 2656048
469 : 2670787
470 : 2685590
471 : 2700521
472 : 2715484
473 : 2730511
474 : 2745602
475 : 2760821
476 : 2776104
477 : 2791515
478 : 2807054
479 : 2822849
480 : 2838660
481 : 2854503
482 : 2870378
483 : 2886317
484 : 2902288
485 : 2918323
486 : 2934422
487 : 2950649
488 : 2966908
489 : 2983231
490 : 2999618
491 : 3016133
492 : 3032712
493 : 3049419
494 : 3066254
495 : 3083345
496 : 3100468
497 : 3117655
498 : 3134906
499 : 3152285
500 : 3169728

三根都有的随机数据

1   : 4
2   : 11
3   : 24
4   : 42
5   : 68
6   : 102
7   : 143
8   : 191
9   : 249
10  : 319
11  : 399
12  : 489
13  : 594
14  : 709
15  : 834
16  : 968
17  : 1116
18  : 1278
19  : 1454
20  : 1644
21  : 1858
22  : 2086
23  : 2330
24  : 2588
25  : 2866
26  : 3168
27  : 3488
28  : 3824
29  : 4187
30  : 4566
31  : 4967
32  : 5381
33  : 5817
34  : 6271
35  : 6747
36  : 7245
37  : 7783
38  : 8335
39  : 8903
40  : 9485
41  : 10087
42  : 10713
43  : 11357
44  : 12017
45  : 12705
46  : 13413
47  : 14149
48  : 14903
49  : 15685
50  : 16495
51  : 17333
52  : 18199
53  : 19113
54  : 20055
55  : 21029
56  : 22031
57  : 23073
58  : 24163
59  : 25287
60  : 26439
61  : 27642
62  : 28873
63  : 30150
64  : 31448
65  : 32784
66  : 34146
67  : 35546
68  : 36984
69  : 38494
70  : 40018
71  : 41558
72  : 43112
73  : 44686
74  : 46284
75  : 47900
76  : 49532
77  : 51192
78  : 52872
79  : 54580
80  : 56306
81  : 58060
82  : 59842
83  : 61652
84  : 63490
85  : 65376
86  : 67290
87  : 69236
88  : 71210
89  : 73224
90  : 75286
91  : 77382
92  : 79506
93  : 81682
94  : 83890
95  : 86150
96  : 88436
97  : 90766
98  : 93132
99  : 95539
100 : 97987
101 : 100506
102 : 103048
103 : 105612
104 : 108200
105 : 110820
106 : 113482
107 : 116168
108 : 118878
109 : 121628
110 : 124408
111 : 127224
112 : 130070
113 : 132960
114 : 135898
115 : 138873
116 : 141889
117 : 144968
118 : 148088
119 : 151242
120 : 154440
121 : 157694
122 : 161026
123 : 164385
124 : 167769
125 : 171196
126 : 174644
127 : 178119
128 : 181619
129 : 185161
130 : 188737
131 : 192353
132 : 196011
133 : 199745
134 : 203501
135 : 207277
136 : 211075
137 : 214901
138 : 218767
139 : 222653
140 : 226559
141 : 230497
142 : 234463
143 : 238461
144 : 242485
145 : 246545
146 : 250649
147 : 254785
148 : 258957
149 : 263185
150 : 267457
151 : 271769
152 : 276125
153 : 280537
154 : 285029
155 : 289557
156 : 294117
157 : 298733
158 : 303389
159 : 308101
160 : 312847
161 : 317645
162 : 322495
163 : 327393
164 : 332343
165 : 337381
166 : 342463
167 : 347585
168 : 352751
169 : 357973
170 : 363275
171 : 368617
172 : 373999
173 : 379445
174 : 384947
175 : 390513
176 : 396131
177 : 401821
178 : 407599
179 : 413441
180 : 419355
181 : 425381
182 : 431495
183 : 437689
184 : 443971
185 : 450365
186 : 456919
187 : 463539
188 : 470211
189 : 476983
190 : 483811
191 : 490739
192 : 497709
193 : 504755
194 : 511853
195 : 519027
196 : 526277
197 : 533671
198 : 541091
199 : 548539
200 : 556011
201 : 563515
202 : 571063
203 : 578639
204 : 586239
205 : 593879
206 : 601555
207 : 609279
208 : 617031
209 : 624823
210 : 632663
211 : 640543
212 : 648463
213 : 656447
214 : 664483
215 : 672575
216 : 680715
217 : 688919
218 : 697211
219 : 705555
220 : 713939
221 : 722394
222 : 730901
223 : 739490
224 : 748110
225 : 756780
226 : 765496
227 : 774262
228 : 783078
229 : 791982
230 : 800926
231 : 809914
232 : 818940
233 : 828018
234 : 837164
235 : 846356
236 : 855588
237 : 864887
238 : 874238
239 : 883659
240 : 893121
241 : 902645
242 : 912235
243 : 921887
244 : 931601
245 : 941418
246 : 951299
247 : 961250
248 : 971262
249 : 981359
250 : 991558
251 : 1001824
252 : 1012144
253 : 1022565
254 : 1033042
255 : 1043615
256 : 1054229
257 : 1064917
258 : 1075655
259 : 1086465
260 : 1097349
261 : 1108373
262 : 1119421
263 : 1130493
264 : 1141591
265 : 1152725
266 : 1163903
267 : 1175109
268 : 1186343
269 : 1197625
270 : 1208939
271 : 1220293
272 : 1231681
273 : 1243121
274 : 1254613
275 : 1266153
276 : 1277745
277 : 1289425
278 : 1301153
279 : 1312929
280 : 1324757
281 : 1336657
282 : 1348645
283 : 1360685
284 : 1372773
285 : 1384949
286 : 1397173
287 : 1409469
288 : 1421815
289 : 1434245
290 : 1446743
291 : 1459321
292 : 1471983
293 : 1484797
294 : 1497659
295 : 1510569
296 : 1523531
297 : 1536565
298 : 1549687
299 : 1562865
300 : 1576099
301 : 1589429
302 : 1602823
303 : 1616297
304 : 1629839
305 : 1643485
306 : 1657235
307 : 1671081
308 : 1685031
309 : 1699157
310 : 1713379
311 : 1727697
312 : 1742119
313 : 1756685
314 : 1771427
315 : 1786267
316 : 1801191
317 : 1816279
318 : 1831439
319 : 1846731
320 : 1862097
321 : 1877603
322 : 1893193
323 : 1908923
324 : 1924793
325 : 1940935
326 : 1957103
327 : 1973299
328 : 1989519
329 : 2005771
330 : 2022067
331 : 2038391
332 : 2054739
333 : 2071127
334 : 2087551
335 : 2104023
336 : 2120523
337 : 2137063
338 : 2153651
339 : 2170279
340 : 2186947
341 : 2203679
342 : 2220463
343 : 2237303
344 : 2254191
345 : 2271143
346 : 2288183
347 : 2305275
348 : 2322407
349 : 2339611
350 : 2356871
351 : 2374219
352 : 2391603
353 : 2409043
354 : 2426539
355 : 2444091
356 : 2461699
357 : 2479403
358 : 2497159
359 : 2514971
360 : 2532831
361 : 2550755
362 : 2568767
363 : 2586835
364 : 2604951
365 : 2623147
366 : 2641415
367 : 2659779
368 : 2678199
369 : 2696699
370 : 2715295
371 : 2733971
372 : 2752727
373 : 2771611
374 : 2790599
375 : 2809699
376 : 2828895
377 : 2848219
378 : 2867719
379 : 2887319
380 : 2906991
381 : 2926799
382 : 2946703
383 : 2966775
384 : 2986897
385 : 3007103
386 : 3027377
387 : 3047731
388 : 3068169
389 : 3088759
390 : 3109393
391 : 3130067
392 : 3150785
393 : 3171559
394 : 3192413
395 : 3213307
396 : 3234241
397 : 3255239
398 : 3276293
399 : 3297411
400 : 3318581
401 : 3339823
402 : 3361153
403 : 3382547
404 : 3404013
405 : 3425591
406 : 3447257
407 : 3469003
408 : 3490837
409 : 3512783
410 : 3534889
411 : 3557067
412 : 3579309
413 : 3601663
414 : 3624097
415 : 3646643
416 : 3669257
417 : 3691975
418 : 3714797
419 : 3737712
420 : 3760728
421 : 3783911
422 : 3807177
423 : 3830513
424 : 3853933
425 : 3877457
426 : 3901135
427 : 3924881
428 : 3948699
429 : 3972629
430 : 3996661
431 : 4020801
432 : 4045039
433 : 4069409
434 : 4093947
435 : 4118594
436 : 4143370
437 : 4168337
438 : 4193465
439 : 4218723
440 : 4244145
441 : 4269767
442 : 4295691
443 : 4321706
444 : 4347794
445 : 4374021
446 : 4400317
447 : 4426736
448 : 4453214
449 : 4479802
450 : 4506460
451 : 4533227
452 : 4560101
453 : 4587178
454 : 4614282
455 : 4641416
456 : 4668576
457 : 4695772
458 : 4723014
459 : 4750288
460 : 4777590
461 : 4804940
462 : 4832328
463 : 4859768
464 : 4887240
465 : 4914760
466 : 4942332
467 : 4969952
468 : 4997620
469 : 5025368
470 : 5053170
471 : 5081032
472 : 5108946
473 : 5136932
474 : 5165010
475 : 5193148
476 : 5221334
477 : 5249608
478 : 5277942
479 : 5306372
480 : 5334846
481 : 5363392
482 : 5392002
483 : 5420681
484 : 5449429
485 : 5478296
486 : 5507212
487 : 5536178
488 : 5565192
489 : 5594270
490 : 5623434
491 : 5652650
492 : 5681914
493 : 5711258
494 : 5740668
495 : 5770162
496 : 5799714
497 : 5829350
498 : 5859082
499 : 5888891
500 : 5918781

数据:

100 100
1 2 3 1 1 1 2 3 1 2 2 1 3 1 2 1 2 1 1 3 2 1 2 1 1 1 3 2 2 1 1 3 1 2 2 3 1 1 1 3 2 2 1 3 2 3 3 2 2 3 1 1 2 1 3 2 2 3 2 1 2 2 3 1 1 2 2 2 2 2 2 3 2 1 2 2 2 2 3 3 2 3 1 1 3 1 2 2 3 2 3 2 1 1 3 1 3 3 3 3
1 3 2 3 3 1 3 2 3 3 1 3 1 3 3 3 3 2 2 1 3 1 1 3 3 1 1 2 1 3 3 2 1 2 1 3 2 2 2 1 2 2 1 2 1 1 1 3 3 3 3 2 1 2 3 3 3 3 2 2 2 2 2 1 1 2 3 1 2 2 1 3 1 1 3 2 2 2 1 1 3 2 2 1 3 1 3 1 1 3 2 2 3 2 1 2 1 3 2 1

这个似乎就是对的了- -..

#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 2000100
using namespace std;
#define pushvc(_v,_t) _v.push_back(_t)
#define hashmod 998244353
namespace graph{
    struct node;
    struct edge{
        node* t;
        edge* n;
        edge(node* t=NULL,edge* n=NULL):t(t),n(n){}
    };
    struct node{
        int id;
        edge* h;
        node(int id=0,edge* h=NULL):id(id),h(h){}
    };
    struct graph{ // utility for storing a graph, and later convert to a tree
        node nodes[maxn];
        edge edges[maxn<<1];
        int edgeSize,nodeCount;
        graph(int edgeSize=0,int nodeCount=0):edgeSize(edgeSize),nodeCount(nodeCount){}
        inline void addedge(node* a,node* b){
            ++edgeSize;
            edges[edgeSize]=(edge){b,a->h};
            a->h=edges+edgeSize;
        }
        inline void bidedge(node* a,node* b){
            addedge(a,b); addedge(b,a);
        }
        inline node* newNode(){
            ++nodeCount;
            nodes[nodeCount].id=nodeCount;
            return nodes+nodeCount;
        }
        inline node& operator[](int n){
            return nodes[n];
        }
        inline node* operator+ (int n){
            return nodes+n;
        }
    };
    struct unrooted_tree{
        struct node_data{
            int tot_sub,max_sub;
        } nt_nds[maxn];
        graph grf;
        int size;
        node* wc[10];
        int sizewc;
        int mimasubtree;
        unrooted_tree(int _size=0){
            size=_size;
            if(_size){
                while(_size){
                    grf.newNode();
                    --_size;
                }
            }
        }
        inline int _gwc_dfs(node* n,node* f){
            nt_nds[n->id].max_sub=0;
            nt_nds[n->id].tot_sub=1;
            for(edge* i=n->h;i;i=i->n){
                if(i->t == f) continue;
                int q=_gwc_dfs(i->t,n);
                nt_nds[n->id].tot_sub+=q;
                if(q > nt_nds[n->id].max_sub) nt_nds[n->id].max_sub=q;
            }
            if((size-nt_nds[n->id].tot_sub) > nt_nds[n->id].max_sub)
                nt_nds[n->id].max_sub=size-nt_nds[n->id].tot_sub;
            return nt_nds[n->id].tot_sub;
        }
        inline void pushwc(node* p){
            wc[++sizewc]=p;
        }
        inline int getwcs(){ // get weight centers, return the number of weight centers.
            _gwc_dfs(grf+1,NULL);
            mimasubtree=0x7fffffff;
            sizewc=0;
            for(int i=1;i<=size;++i) if(nt_nds[i].max_sub < mimasubtree) mimasubtree=nt_nds[i].max_sub;
            for(int i=1;i<=size;++i) if(nt_nds[i].max_sub== mimasubtree) pushwc(grf+i);
            return sizewc;
        }
        FILE* otd; // for dot file output
        inline void _print_dfs(node* n,node* f){
            fprintf(otd,"A%d[label=\"#%d\"];\n",n->id,n->id);
            for(edge* i=n->h;i;i=i->n){
                if(i->t == f) continue;
                fprintf(otd,"A%d -> A%d;\n",n->id,i->t->id);
                _print_dfs(i->t,n);
            }
        }
        inline void print_dot(node* asroot){
            fprintf(otd,"digraph{\n"
                    "    node[color=\"#2266ff\",fillcolor=\"#aaccff\",fontname=\"Courier\",regular=true];\n");
            _print_dfs(asroot,NULL);
            fprintf(otd,"}\n");
        }
        inline void openOutputFile(const char* filename){
            if(otd) fclose(otd),otd=NULL;
            otd=fopen(filename,"w");
        }
    };
//    FILE* otd; // for dot file output
//    inline void mopenOutputFile(const char* filename){
//        if(otd) fclose(otd),otd=NULL;
//        otd=fopen(filename,"w");
//    }
    struct rooted_tree{
        int size,maxdepth,hash;
        node* root;
        vector<rooted_tree*> sons;
        void build(node* p,node* f);
        void print();
    };
    inline int cmp_same (rooted_tree* a,rooted_tree* b){
        if(a->size - b->size) return a->size - b->size;
        if(a->maxdepth - b->maxdepth) return a->maxdepth - b->maxdepth;
        if(a->hash - b->hash) return a->hash - b->hash;
        int ax=a->sons.size(),bx=b->sons.size();
        if(ax - bx) return ax - bx;
        for(int i=0;i<ax;++i){
            int q=cmp_same(a->sons[i],b->sons[i]);
            if(q) return q;
        }
        return 0;
    }
    inline bool cmp_build(const rooted_tree* a,const rooted_tree* b){
        if(a->size - b->size) return a->size > b->size;
        if(a->maxdepth - b->maxdepth) return a->maxdepth > b->maxdepth;
        if(a->hash - b->hash) return a->hash > b->hash;
        int ax=a->sons.size(),bx=b->sons.size();
        if(ax - bx) return ax > bx;
        for(int i=0;i<ax;++i){
            int q=cmp_same(a->sons[i],b->sons[i]);
            if(q) return q>0;
        }
        return 0;
    }
    void rooted_tree::build(node* p,node* f){
        root=p; size=1; maxdepth=0; hash=1;
        for(edge* i=p->h;i;i=i->n){
            if(i->t == f) continue;
            rooted_tree* s1=new rooted_tree;
            s1->build(i->t,p);
            pushvc(sons,s1);
            size+=s1->size;
            if(s1->maxdepth > maxdepth) maxdepth=s1->maxdepth;
        }
        ++maxdepth;
        sort(sons.begin(),sons.end(),cmp_build);
        for(int i=0,_=sons.size();i<_;++i){
            hash=((long long)hash+(long long)sons[i]->hash*(long long)(i+1))%hashmod;
            //some very weak hash function, because the time complexity is
            //provided O(nlogn) total, so it is just a speed up
        }
    }
    bool isiso(unrooted_tree* a,unrooted_tree* b){
        if(a->size != b->size) return 0;
        a->getwcs();
        int q=b->getwcs();
        if(a->sizewc != b->sizewc) return 0;
        if(a->mimasubtree != b->mimasubtree) return 0;
        rooted_tree* ptree=new rooted_tree;
        ptree->build(a->wc[1],NULL); // build an minimized tree
        for(int i=1;i<=q;++i){
            rooted_tree* qtree=new rooted_tree;
            qtree->build(b->wc[i],NULL);
            if(!cmp_same(ptree,qtree)) return 1;
        }
        return 0;
    }
    inline unrooted_tree* readTree_byEdge(){
        int n;
        scanf("%d",&n);
        unrooted_tree* p=new unrooted_tree(n);
        for(int i=1,a,b;i<n;++i){
            scanf("%d%d",&a,&b);
            p->grf.bidedge(p->grf+a,p->grf+b);
        }
        return p;
    }
    void rooted_tree::print(){
        printf("Access node %d with %d sons,Fields: size %d maxdepth %d hash%d\n",
            root->id,sons.size(),size,maxdepth,hash);
        if(sons.size()){
            printf("Sons:");
            for(int i=0;i<sons.size();++i) printf("%d ",sons[i]->root->id);
            putchar('\n');
            for(int i=0;i<sons.size();++i) sons[i]->print();
        }
    }
}
using namespace graph;
int main(){
    unrooted_tree* p=readTree_byEdge();
    unrooted_tree* q=readTree_byEdge();
//    p->openOutputFile("out.dot");
//    p->getwcs();
//    p->print_dot(p->wc[1]);
//    printf("%d %d %d\n",p->wc[1]->id,p->mimasubtree,p->wc[2]->id);
//    rooted_tree* k=new rooted_tree;
//    k->build(p->wc[1],NULL);
//    k->print();
//    rooted_tree* kq=new rooted_tree;
//    if(p->wc[2]){
//        kq->build(p->wc[2],NULL);
//        kq->print();
//        printf("%s\n",cmp_same(k,kq)?"Diff":"Same");
//    }
    printf("%s\n",isiso(p,q)?"Same":"Diff");
    return 0;
}

似乎跑得很慢?当然可以跑得更快的...

我知道这是一道傻逼题...但是考场上并没有调出来...我还没有打暴力...恩..考挂自己弱...

先考虑一条链的情况...我们发现,最优解肯定要考虑减小最长链,其次考虑次长的,...那么我们设$L_i$为第i长的链,我们需要删去的一条边一定是对于某个正整数k,$\bigcup_{i=1}^kL_i$上的最长边,那么我们把这些区间处理出来每次更新,就有了一个复杂度为$O(n)$的优秀算法.

对于一棵树的情况,考虑处理出它的最长链,在这条链上做就可以了.

yyhs数据有一个点我比他优? 感觉是我写炸了...窝要去调调...

考场代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
///ri gou qu ba CCF
inline int max(int a,int b){
    if(a<b) return b; else return a;
}
#define maxn 300010
struct sw{
    int nx[maxn];
    int si;
    inline int qmaxe(int n,int e){
        if(n==si) return nx[1]-e; else return max(nx[1]-e,nx[n+1]);
    }
    inline int push(int n){
        ++si;
        nx[si]=n;
    }
} sww;
struct ed{
    int t,n,v;
} fy[maxn*2];
int h[maxn],sie;
inline void ae(int f,int t,int v){
    ++sie;
    fy[sie]=(ed){t,h[f],v};
    h[f]=sie;
}
inline int l2e(int a){
    float p=(float)a;
    return (((*(int*)&p)>>23)+1)&31;
}
struct tree{
    int fa[maxn],de[maxn],deu[maxn],si;
    int seq[maxn*4],seqL,reseq[maxn];
    int st[maxn*4][21];
    inline void logSeq(int n){ seq[seqL++]=n; }
    inline void dfsBuild(int nw,int fax,int fad,int dex){
        de[nw]=fad,deu[nw]=dex,fa[nw]=fax;
        reseq[nw]=seqL;
        logSeq(nw);
        for(int i=h[nw],_;i;i=fy[i].n){
            _=fy[i].t;
            if(_==fa[nw]) continue;
            dfsBuild(_,nw,fad+1,dex+fy[i].v);
            logSeq(nw);
        }
    }
    inline int mindep(int a,int b){
        if(de[a]<de[b]) return a; else return b;
    }
    inline void genSt(){
        int t=l2e(seqL);
        for(int i=0;i<seqL;++i) st[i][0]=seq[i];
        for(int i=2,j=1;i<=seqL;i<<=1,++j){
            register int q=i>>1;
            for(int k=0,_=seqL-i;k<=_;++k){
                st[k][j]=mindep(st[k][j-1],st[k+q][j-1]);
            }
        }
    }
    inline int getmin(int a,int b){
        if(b<a) std::swap(a,b);
        int l=b-a+1;
        int le=l2e(l);
        int lk=1<<le;
        return mindep(st[a][le],st[b-le+1][le]);
    }
    inline int LCA(int a,int b){
        return getmin(reseq[a],reseq[b]);
    }
    inline void build(int n){
        si=n;
        dfsBuild(1,0,0,0);genSt();
    }
    int impPoints[maxn],impL,blt[maxn];//important points, (length), belongs to
    int impDs[maxn],mxl,mxr,mxn;
    bool ft;
    inline int getMax(int l,int r){
        if(!ft){
            mxl=l,mxr=l-1;
            ft=1;
        } 
        while(mxl>l){
            --mxl;
            mxn=max(impDs[mxl],mxn);
        }
        while(mxr<r){
            ++mxr;
            mxn=max(impDs[mxr],mxn);
        }
    }
    int resSes;
    inline void dfsResec(int nq,int fa){
        blt[nq]=resSes;
        for(int t=h[nq],_;t;t=fy[t].n){
            if(_==fa) continue;
            dfsResec(_,nq);
        }
    }
    inline void resec(int n){
        resSes=n;
        blt[impPoints[n]]=n;
        for(int t=h[impPoints[n]],_;t;t=fy[t].n){
            _=fy[t].t;
            if(_==impPoints[n-1]) continue;
            if(_==impPoints[n+1]) continue;
            dfsResec(_,impPoints[n]);
        }
    }
} tr;
struct path{
    int f,t,p,len;
    path(int f=0,int t=0):f(f),t(t){}
    inline int lengthTot(){
        p=tr.LCA(f,t);
        return tr.deu[f]+tr.deu[t]-(tr.deu[p]<<1);
    }
    inline void rd(){
        scanf("%d%d",&f,&t);
        len=lengthTot();
    }
} paa[maxn];
inline bool cmp(const path& a,const path& b){
    return a.len<b.len;
}
int n,m,imps[maxn],sl;
inline void ps1(int n){
    ++tr.impL;
    tr.impPoints[tr.impL]=n;
}
inline void psl(int n){
    static int s=1;
    tr.impDs[s]=n;
    ++s;
}
inline void ps2(int n){
    ++sl;
    imps[sl]=n;
}
inline void getImpPo(){//get important points
    int tx=paa[1].f;
    while(tx!=paa[1].p){
        ps1(tx);
        psl(tr.deu[tx]-tr.deu[tr.fa[tx]]);
        tx=tr.fa[tx];
    }
    ps1(paa[1].p);
    tx=paa[1].t;
    while(tx!=paa[1].p){
        ps2(tx);
    }
    while(sl){
        tx=imps[sl];
        ps1(tx);
        psl(tr.deu[tx]-tr.deu[tr.fa[tx]]);
        --sl;
    }
}
struct range{
    int l,r;
    bool valid;
    inline range(int l=0,int r=0,bool testValid=1):l(l),r(r){
        if(testValid) if(l>r) std::swap(l,r);
    }
    inline range operator*(range b){ // intersect
        range p(l,r,0);
        if(b.l>l) p.l=b.l;
        if(b.r<r) p.r=b.r;
        return p;
    }
    inline bool hasRg(){
        return r>=l;
    }
} rgs[maxn];
int rgl;
inline void pushRange(range f){
    rgs[++rgl]=f;
}
inline range top(){
    return rgs[rgl];
}
inline bool same(range a,range b){
    return a.l==b.l && a.r==b.r;
}
inline void rt(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,v;i<n;++i){
        scanf("%d%d%d",&a,&b,&v);
        ae(a,b,v); ae(b,a,v);
    }
    tr.build(n);
    for(int i=1;i<=m;++i) paa[i].rd();
    std::sort(paa+1,paa+m+1,cmp);
    getImpPo();
    for(int i=1;i<=m;++i) sww.push(paa[i].len);
    for(int i=1;i<=m;++i){
        pushRange(top()*range(tr.blt[paa[i].f],tr.blt[paa[i].t]));
    }
}
inline void tensen(int &a,int b){
    if(a>b) a=b;
}
int main(){
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
    rt();
    int i=m;
    int maxp=0x7fffffff;
    while(!rgs[i].hasRg()){ --i; }
    while(i){
        tensen(maxp,sww.qmaxe(i,tr.getMax(rgs[i].l,rgs[i].r)));
        --i;
    }
    printf("%d\n",maxp);
    return 0;
}

调出来的代码

#include <cstdio>
#include <algorithm>
#include <cstring>
///ri gou qu ba CCF
inline int max(int a,int b){
    if(a<b) return b; else return a;
}
#define maxn 300010
struct sw{
    int nx[maxn];
    int si;
    inline int qmaxe(int n,int e){
        if(n==si) return nx[1]-e; else return max(nx[1]-e,nx[n+1]);
    }
    inline int push(int n){
        ++si;
        nx[si]=n;
    }
} sww;
struct ed{
    int t,n,v;
} fy[maxn*2];
int h[maxn],sie;
inline void ae(int f,int t,int v){
    ++sie;
    fy[sie]=(ed){t,h[f],v};
    h[f]=sie;
}
inline int l2e(int a){
    float p=(float)a;
    return (((*(int*)&p)>>23)+1)&31;
}
struct tree{
    int fa[maxn],de[maxn],deu[maxn],si;
    int seq[maxn*4],seqL,reseq[maxn];
    int st[maxn*4][21];
    inline void logSeq(int n){ seq[seqL++]=n; }
    inline void dfsBuild(int nw,int fax,int fad,int dex){
        de[nw]=fad,deu[nw]=dex,fa[nw]=fax;
        reseq[nw]=seqL;
        logSeq(nw);
        for(int i=h[nw],_;i;i=fy[i].n){
            _=fy[i].t;
            if(_==fa[nw]) continue;
            dfsBuild(_,nw,fad+1,dex+fy[i].v);
            logSeq(nw);
        }
    }
    inline int mindep(int a,int b){
        if(de[a]<de[b]) return a; else return b;
    }
    inline void genSt(){
        int t=l2e(seqL);
        for(int i=0;i<seqL;++i) st[i][0]=seq[i];
        for(int i=2,j=1;i<=seqL;i<<=1,++j){
            register int q=i>>1;
            for(int k=0,_=seqL-i;k<=_;++k){
                st[k][j]=mindep(st[k][j-1],st[k+q][j-1]);
            }
        }
    }
    inline int getmin(int a,int b){
        if(b<a) std::swap(a,b);
        int l=b-a+1;
        int le=l2e(l);
        int lk=1<<le;
        return mindep(st[a][le],st[b-lk+1][le]);
    }
    inline int LCA(int a,int b){
        return getmin(reseq[a],reseq[b]);
    }
    inline void build(int n){
        si=n;
        dfsBuild(1,0,0,0);genSt();
    }
    int impPoints[maxn],impL,blt[maxn];//important points, (length), belongs to
    int impDs[maxn],mxl,mxr,mxn;
    bool ft;
    inline int getMax(int l,int r){
        if(!ft){
            mxl=l,mxr=l-1;
            ft=1;
        } 
        while(mxl>l){
            --mxl;
            mxn=max(impDs[mxl],mxn);
        }
        while(mxr<r){
            ++mxr;
            mxn=max(impDs[mxr],mxn);
        }
        return mxn;
    }
    int resSes;
    inline void dfsResec(int nq,int fa){
        blt[nq]=resSes;
        for(int t=h[nq],_;t;t=fy[t].n){
            _=fy[t].t;
            if(_==fa) continue;
            dfsResec(_,nq);
        }
    }
    inline void resec(int n){
        resSes=n; blt[impPoints[n]]=n;
        for(int t=h[impPoints[n]],_;t;t=fy[t].n){
            _=fy[t].t;
            if(_==impPoints[n-1]) continue;
            if(_==impPoints[n+1]) continue;
            dfsResec(_,impPoints[n]);
        }
    }
} tr;
struct path{
    int f,t,p,len;
    path(int f=0,int t=0):f(f),t(t){}
    inline int lengthTot(){
        p=tr.LCA(f,t);
        return tr.deu[f]+tr.deu[t]-(tr.deu[p]<<1);
    }
    inline void rd(){
        scanf("%d%d",&f,&t);
        len=lengthTot();
    }
} paa[maxn];
inline bool cmp(const path& a,const path& b){
    return a.len>b.len;
}
int n,m,imps[maxn],sl;
inline void ps1(int n){
    ++tr.impL;
    tr.impPoints[tr.impL]=n;
}
inline void psl(int n){
    static int s=1;
    tr.impDs[s]=n;
    ++s;
}
inline void ps2(int n){
    ++sl;
    imps[sl]=n;
}
inline void getImpPo(){//get important points
    int tx=paa[1].f;
    while(tx!=paa[1].p){
        ps1(tx);
        psl(tr.deu[tx]-tr.deu[tr.fa[tx]]);
        tx=tr.fa[tx];
    }
    ps1(paa[1].p);
    tx=paa[1].t;
    while(tx!=paa[1].p){
        ps2(tx);
        tx=tr.fa[tx];
    }
    while(sl){
        tx=imps[sl];
        ps1(tx);
        psl(tr.deu[tx]-tr.deu[tr.fa[tx]]);
        --sl;
    }
    for(int i=1;i<=tr.impL;++i) tr.resec(i);
}
struct range{
    int l,r;
    inline range(int _l=0,int _r=0x7fffffff,bool testValid=1){
        l=_l,r=_r;
        if(testValid) if(l>r) std::swap(l,r);
    }
    inline range operator*(range b){ // intersect
        range p(l,r,0);
        if(b.l>l) p.l=b.l;
        if(b.r<r) p.r=b.r;
        return p;
    }
    inline bool hasRg(){
        return r>=l;
    }
} rgs[maxn];
int rgl;
inline void pushRange(range f){
    rgs[++rgl]=f;
}
inline range top(){
    return rgs[rgl];
}
inline bool same(range a,range b){
    return a.l==b.l && a.r==b.r;
}
inline void rt(){
    scanf("%d%d",&n,&m);
    for(int i=1,a,b,v;i<n;++i){
        scanf("%d%d%d",&a,&b,&v);
        ae(a,b,v); ae(b,a,v);
    }
    tr.build(n);
    for(int i=1;i<=m;++i) paa[i].rd();
    std::sort(paa+1,paa+m+1,cmp);
    getImpPo();
    for(int i=1;i<=m;++i) sww.push(paa[i].len);
    for(int i=1;i<=m;++i){
        pushRange(top()*range(tr.blt[paa[i].f],tr.blt[paa[i].t]));
    }
}
inline void tensen(int &a,int b){
    if(a>b) a=b;
}
int main(){
    freopen("transport.in","r",stdin);
    freopen("transport.out","w",stdout);
    rt();
    int i=m;
    int maxp=0x7fffffff;
    while(!rgs[i].hasRg()){ --i; }
    while(i){
        tensen(maxp,sww.qmaxe(i,tr.getMax(rgs[i].l,rgs[i].r)));
        --i;
    }
    printf("%d\n",maxp);
    return 0;
}

我没有写$O(n)$ LCA.

都有点不会写了...顺便用NTT干一发Complex FFT.不开挂跑了446ms,算是达到心理预期了吧...http://uoj.ac/submission/27715

PS. 居然有人用Karatsuba过了这题...什么时候我要写写Toom-3...

Upd. Toom-3代码写过一些了虽然在高精度里面...https://github.com/iamstupid/toybi