QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#554575#3000. 希望nfls_vjudge100 ✓1156ms405716kbC++147.6kb2024-09-09 12:20:032024-09-09 12:20:05

Judging History

你现在查看的是最新测评结果

  • [2024-09-09 12:20:05]
  • 评测
  • 测评结果:100
  • 用时:1156ms
  • 内存:405716kb
  • [2024-09-09 12:20:03]
  • 提交

answer

// Hydro submission #66de77672385295eec0656d1@1725855591969
/* name: P5291
 * author: 5ab
 * created at: 2024-02-05
 */
#include <iostream>
#include <cassert>
#include <vector>
#include <tuple>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;
const int N = 1e6, mod = 998244353;

struct info
{
	int mu, imu, ad, zs;
}
tf[N], tf2[N];
int hd[N], des[N * 2], nxt[N * 2], ff[N], f[N], f2[N], g[N], st[N], ed[N], mxd[N], fac[N + 1], ifac[N + 1], ec = 0, ind = 0;
vector<pair<int, int>> buc[N];
vector<pair<int, int>> stk[N], fs[N];
vector<int> tr[N];

void add(int s, int t)
{
	des[ec] = t;
	nxt[ec] = hd[s];
	hd[s] = ec++;
}

void dfs0(int id, int fa)
{
	mxd[id] = ff[id] = 1;
	for (int p = hd[id], dst; p != -1; p = nxt[p])
	{
		dst = des[p];
		if (dst != fa)
		{
			dfs0(dst, id);
			buc[mxd[dst]].emplace_back(id, dst);
			chmax(mxd[id], mxd[dst] + 1);
			ff[id] = 1ll * ff[id] * ff[dst] % mod;
		}
	}
	ff[id] = (ff[id] + 1) % mod;
}

ll qpow(ll bs, ll ix)
{
	ll mul = bs, ret = 1;
	while (ix)
	{
		if (ix & 1)
			ret = (ret * mul) % mod;
		mul = (mul * mul) % mod;
		ix >>= 1;
	}
	return ret;
}

int recvg(int x, int i, const info& t) {
	return ((i >= t.zs ? 0 : 1ll * t.mu * x) + t.ad) % mod;
}
int recvf(int x, int i, const info& t) {
	return ((i < t.zs ? 0 : 1ll * t.mu * x) + t.ad) % mod;
}
int recv(int x, int i) {
	// cerr << x << " " << ssz(fs[x]) << " " << i << endl;
	return recvf(fs[x][i].first, i, tf[x]);
}

void mergef(int id, int x, int lsf, int ilsf)
{
	// cerr << lsf << " " << ilsf << " " << 1ll * lsf * ilsf % mod << endl;
	if (lsf)
		tf[id].imu = 1ll * tf[id].imu * ilsf % mod;
	for (int i = ssz(fs[x]) - 1, j = ssz(fs[id]) - 1; i >= 0; i--, j--)
	{
		int cv = 1ll * recv(x, i) * recv(id, j) % mod;
		// cerr << cv << endl;
		fs[id][j].first = 1ll * (cv - 1ll * tf[id].ad * lsf % mod + mod) * tf[id].imu % mod;
	}
	tf[id].ad = 1ll * tf[id].ad * lsf % mod;
	if (lsf)
		tf[id].mu = 1ll * tf[id].mu * lsf % mod;
	else
	{
		int dv = ssz(fs[id]) - ssz(fs[x]);
		for (int i = dv; i < ssz(fs[id]); i++)
			fs[id][i].first = recv(id, i);
		tf[id] = { 1, 1, 0, dv };
	}
}

int l;
void dfs1(int id)
{
	tf[id] = { 1, 1, 0, 0 };
	// cerr << id << endl;
	st[id] = ind++;
	for (auto x : tr[id])
	{
		// cerr << x << " " << id << endl;
		dfs1(x);
		if (fs[id].empty())
		{
			swap(fs[x], fs[id]);
			tf[id] = tf2[x] = tf[x];
			continue;
		}
		mergef(id, x, ff[x], 1ll * ifac[x + 1] * fac[x] % mod);
		int dv = ssz(fs[id]) - ssz(fs[x]);
		for (int i = dv; i < ssz(fs[id]); i++)
			stk[fs[id][i].second].emplace_back(fs[id][i].first, st[x]);
		tf2[x] = tf[id];
	}
	int ev = 1ll * (1 - tf[id].ad + mod) * tf[id].imu % mod;
	fs[id].emplace_back(ev, id);
	stk[id].emplace_back(ev, st[id]);
	(tf[id].ad += 1) %= mod;
	f[id] = recv(id, ssz(fs[id]) - 1 - min(mxd[id] - 1, l));
	if (l > 0)
		f2[id] = recv(id, ssz(fs[id]) - 1 - min(mxd[id] - 1, l - 1));
	ed[id] = ind;
}

void dfs2(int id, vector<pair<int, int>>& gs, info tg)
{
	assert(ssz(gs) == mxd[id]);
	g[id] = recvg(gs.back().first, ssz(gs) - 1, tg);
	gs.pop_back();
	if (gs.empty())
		return;
	int lsf = 1, ilsf = 1;
	for (int i = ssz(tr[id]) - 1; i > 0; i--)
	{
		int x = tr[id][i];
		vector<pair<int, int>> ngs(mxd[x]);
		for (int y = x, j = ssz(ngs) - 1, k = ssz(gs) - 1; y != -1; y = tr[y].empty() ? -1 : tr[y][0], j--, k--)
		{
			ngs[j] = { recvg(gs[k].first, k, tg), y };
			// cerr << id << " " << j << " " << recvg(gs[k].first, k, tg) << endl;
		}
		if (i < ssz(tr[id]) - 1)
		{
			int y = tr[id][i + 1];
			for (int j = ssz(fs[y]) - l + 1, k = ssz(ngs) - 1; k >= 0 && j < ssz(fs[y]); j++, k--)
			{
				ngs[k].first = 1ll * ngs[k].first * recv(y, max(0, j)) % mod;
				// cerr << id << " " << k << " " << recv(y, max(0, j)) << endl;
			}
		}
		int y = tr[id][i - 1];
		// cerr << id << " " << x << " " << y << endl;
		for (int j = max(0, ssz(ngs) - l + 1); j < ssz(ngs); j++)
		{
			int k = max(0, ssz(gs) - (l - (ssz(ngs) - j))), p = gs[k].second;
			// cerr << p << " " << ssz(stk[p]) << endl;
			while (!stk[p].empty() && stk[p].back().second >= ed[y])
				stk[p].pop_back();
			assert(!stk[p].empty());
			int &v = ngs[j].first;
			v = 1ll * v * recvf(stk[p].back().first, k, tf2[y]) % mod;
			// cerr << id << " " << j << " " << recvf(stk[p].back().first, k, tf2[y]) << endl;
		}
		if (ssz(ngs) >= l)
			end(ngs)[-l].first = 1;
		dfs2(x, ngs, { 1, 1, 1, ssz(ngs) });
		if (i < ssz(tr[id]) - 1)
		{
			int y = tr[id][i + 1];
			mergef(x, y, lsf, ilsf);
		}
		lsf = 1ll * lsf * ff[x] % mod, ilsf = 1ll * ilsf * ifac[x + 1] % mod * fac[x] % mod;
	}
	if (ssz(tr[id]) > 1)
	{
		int y = tr[id][1];
		// cerr << lsf << " " << ilsf << " " << 1ll * lsf * ilsf % mod << endl;
		if (lsf)
			tg.imu = 1ll * tg.imu * ilsf % mod;
		// cerr << ssz(gs) << " " << ssz(fs[y]) << endl;
		for (int j = 0, k = ssz(gs) - (l - ssz(fs[y])); k >= 0 && j < ssz(fs[y]); j++, k--)
			if (k < ssz(gs))
			{
				// cerr << id << " " << k << " " << recvg(gs[k].first, k, tg) << " " << recv(y, j) << endl;
				int cv = 1ll * recvg(gs[k].first, k, tg) * recv(y, j) % mod;
				gs[k].first = 1ll * (cv - 1ll * tg.ad * lsf % mod + mod) * tg.imu % mod;
				// cerr << gs[k].first << " " << recvg(gs[k].first, k, tg) << endl;
			}
	// cerr << gs.back().first << " " << recvg(gs.back().first, ssz(gs) - 1, tg) << endl;
		tg.ad = 1ll * tg.ad * lsf % mod;
		if (lsf)
			tg.mu = 1ll * tg.mu * lsf % mod;
		else
		{
			// cerr << "? " << ssz(fs[y]) << " " << ssz(gs) << endl;
			int dv = ssz(gs) + ssz(fs[y]) - l;
			for (int i = max(0, ssz(gs) - l + 1); i < dv && i < ssz(gs); i++)
				gs[i].first = recvg(gs[i].first, i, tg);
			tg = { 1, 1, 0, dv };
		}
	}
	if (ssz(gs) >= l)
		end(gs)[-l].first = 1ll * (1 - tg.ad + mod) * tg.imu % mod;
	(tg.ad += 1) %= mod;
	// cerr << gs.back().first << " " << recvg(gs.back().first, ssz(gs) - 1, tg) << endl;
	
	dfs2(tr[id][0], gs, tg);
}

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, k;
	
	cin >> n >> l >> k;
	fill(hd, hd + n, -1);
	for (int i = 1, x, y; i < n; i++)
	{
		cin >> x >> y, x--, y--;
		add(x, y), add(y, x);
	}
	dfs0(0, -1);
	
	for (int i = n - 1; i >= 0; i--)
		for (auto [p, x] : buc[i])
		{
			// cerr << p << " --> " << x << endl;
			tr[p].emplace_back(x);
		}
	
	fac[0] = 1;
	for (int i = 0; i < n; i++)
		fac[i + 1] = 1ll * fac[i] * (ff[i] ? ff[i] : 1) % mod;
	ifac[n] = qpow(fac[n], mod - 2);
	for (int i = n; i > 0; i--)
		ifac[i - 1] = 1ll * ifac[i] * (ff[i - 1] ? ff[i - 1] : 1) % mod;
	
	dfs1(0);
	// for (int i = 0; i < n; i++)
	// {
	// 	cerr << i << " " << st[i] << ": ";
	// 	for (auto [v, p] : stk[i])
	// 		cerr << v << "," << p << " ";
	// 	cerr << endl;
	// }
	vector<pair<int, int>> gs(mxd[0]);
		for (int y = 0, j = ssz(gs) - 1; y != -1; y = tr[y].empty() ? -1 : tr[y][0], j--)
			gs[j] = { 1, y };
	dfs2(0, gs, { 1, 1, 0, ssz(gs) });
	
	// for (int i = 0; i < n; i++)
	// 	cerr << i << ": " << f[i] << " " << f2[i] << " " << g[i] << endl;
	
	int ans = 0;
	for (int i = 0; i < n; i++)
		ans = (ans + qpow(1ll * (f[i] - 1 + mod) * g[i] % mod, k)) % mod;
	if (l > 0)
	{
		for (int i = 1; i < n; i++)
			ans = (ans - qpow(1ll * (f2[i] - 1 + mod) * (g[i] - 1 + mod) % mod, k) + mod) % mod;
	}
	cout << ans << endl;
	
	return 0;
}
// started coding at: 02-05 22:35:16

/*
0: 17 6 1
1: 9 7 7
2: 2 2 16
3: 4 4 11
4: 29 16 2
5: 2 2 4
6: 2 2 4
7: 3 3 6
8: 3 3 6
9: 4 4 11

*/

詳細信息


Pretests


Final Tests

Test #1:

score: 4
Accepted
time: 3ms
memory: 125100kb

input:

16 3 1
15 13
7 5
7 3
13 4
13 11
16 9
13 9
11 2
1 6
14 13
11 12
8 9
7 14
10 6
6 16

output:

1243

result:

ok single line: '1243'

Test #2:

score: 4
Accepted
time: 12ms
memory: 124668kb

input:

10 2 2
6 4
7 3
6 5
8 4
9 8
1 7
2 7
6 7
10 4

output:

9430

result:

ok single line: '9430'

Test #3:

score: 4
Accepted
time: 19ms
memory: 125556kb

input:

10 10 9
2 4
1 8
5 8
7 8
10 9
8 2
1 10
8 3
5 6

output:

287143445

result:

ok single line: '287143445'

Test #4:

score: 4
Accepted
time: 7ms
memory: 124296kb

input:

10 2 10
9 5
4 7
10 4
6 8
3 4
4 6
4 2
5 6
1 10

output:

736013382

result:

ok single line: '736013382'

Test #5:

score: 4
Accepted
time: 7ms
memory: 124420kb

input:

497 497 9
421 44
120 434
367 497
332 122
115 101
5 348
14 144
210 359
141 242
439 276
215 289
303 375
28 77
143 428
151 127
457 288
62 351
421 187
25 261
347 257
344 339
452 474
216 387
144 24
167 148
135 133
178 331
274 50
339 369
60 211
350 292
115 76
393 473
475 387
294 332
43 91
368 81
481 27
95...

output:

331917336

result:

ok single line: '331917336'

Test #6:

score: 4
Accepted
time: 7ms
memory: 124548kb

input:

1000 100 1
382 224
432 411
634 456
768 851
345 832
659 985
177 604
834 849
397 593
156 24
43 819
438 78
188 80
936 395
91 529
959 911
104 355
503 618
164 972
505 652
746 845
907 301
662 531
486 660
360 724
340 112
155 499
308 974
123 97
829 600
709 781
415 678
874 272
675 879
583 881
968 414
769 359...

output:

836607737

result:

ok single line: '836607737'

Test #7:

score: 4
Accepted
time: 27ms
memory: 138264kb

input:

49999 29 10
16726 12082
6732 37340
40485 10847
44869 24166
36684 39431
3249 27243
45483 37633
19260 22383
19143 13528
6706 7421
11839 47225
46922 11790
47525 3196
43850 42710
4893 2839
37556 41101
5873 45077
2696 21251
39836 36172
42780 38464
41481 9865
33864 24756
3474 13763
31198 28752
46506 3786
...

output:

562505285

result:

ok single line: '562505285'

Test #8:

score: 4
Accepted
time: 93ms
memory: 147860kb

input:

99990 95 1
73567 71079
3326 88384
36374 90162
37653 80637
66761 72061
61493 34910
70782 93885
15325 87771
81082 95813
1016 32294
3583 89414
63054 88734
902 70455
89078 71307
5572 73684
90068 2718
7522 87784
1880 77032
9206 13625
40074 66039
84079 94646
7226 26891
10757 47921
52558 82703
77478 24017
...

output:

625332568

result:

ok single line: '625332568'

Test #9:

score: 4
Accepted
time: 91ms
memory: 149800kb

input:

100000 100 9
71142 34813
51716 56682
16198 52726
21972 98808
8782 18661
64438 93384
62968 16698
66396 20240
57089 24568
53302 66919
46404 72330
31924 16432
72942 87322
42977 1430
31924 75941
59006 24077
93987 11904
11298 45520
31924 66491
52351 81769
98877 37816
48438 29764
10467 60332
46402 82645
3...

output:

854741172

result:

ok single line: '854741172'

Test #10:

score: 4
Accepted
time: 1067ms
memory: 405716kb

input:

999992 282751 9
539736 453462
540111 477459
971608 731703
333352 646885
474338 449903
682998 756565
514706 652705
319529 600819
450009 862650
270005 950006
215331 949892
900851 316199
20848 879879
601074 688617
353471 60779
988869 786268
982113 354443
464498 645452
282384 979334
404667 275071
465382...

output:

242487770

result:

ok single line: '242487770'

Test #11:

score: 4
Accepted
time: 36ms
memory: 131316kb

input:

29997 29997 1
17887 27517
28638 28750
17146 20323
2484 14534
14496 9485
28598 1702
16812 20561
12792 10249
21147 12075
26413 21147
23535 12297
12912 2957
16747 4815
3695 4722
15400 11359
12046 1690
23085 4025
15400 29146
11317 21167
21147 27124
26258 22579
27050 28822
21147 12210
23688 24822
16221 1...

output:

208568713

result:

ok single line: '208568713'

Test #12:

score: 4
Accepted
time: 34ms
memory: 131248kb

input:

39999 9999 1
17847 8767
34288 3223
31953 15747
19891 38574
22166 12007
22545 10176
15852 4478
25563 38574
25054 22861
19512 38574
25737 7144
4838 36701
36463 6714
23038 3579
18929 21494
14933 19526
1630 30203
28237 23398
4178 14268
16048 18342
9864 7531
22278 29214
14797 32203
20 13687
3267 27370
29...

output:

622134586

result:

ok single line: '622134586'

Test #13:

score: 4
Accepted
time: 31ms
memory: 135144kb

input:

49937 9618 9
28900 21057
23426 3158
11352 23430
22070 36326
3612 43977
6755 2034
33497 5866
26127 35204
45896 2194
2698 6508
47136 7404
25263 35056
14916 24075
25469 5476
2913 24445
38256 32997
2634 14195
26348 45158
39795 30522
32668 23847
48619 32881
11604 33190
32221 44730
39330 46327
37184 15880...

output:

808296259

result:

ok single line: '808296259'

Test #14:

score: 4
Accepted
time: 59ms
memory: 151404kb

input:

99997 24814 1
70294 6008
96698 51718
85730 12149
7399 68219
19240 98520
6806 60763
60944 9942
95042 84051
52276 11791
92228 26864
31607 4577
50572 55556
91020 39530
99630 58302
46987 75388
13481 8988
73782 79423
13592 71106
68888 24123
69314 52558
1827 1930
2403 39363
71227 97979
62460 62818
93260 8...

output:

889032739

result:

ok single line: '889032739'

Test #15:

score: 4
Accepted
time: 124ms
memory: 156016kb

input:

149934 23430 1
19524 118124
102651 94642
105977 88780
22851 21085
118124 26220
51965 41865
94877 88657
45954 42676
15024 104515
88216 18289
71244 65571
85897 126980
121323 96801
149044 144348
118914 98362
41777 84779
95166 106140
50549 5071
69568 144894
133722 26506
32976 45985
139222 118124
57802 8...

output:

967739919

result:

ok single line: '967739919'

Test #16:

score: 4
Accepted
time: 170ms
memory: 171472kb

input:

199993 199993 10
22574 120810
132171 199046
85192 167635
166147 64640
92778 56014
52056 77741
141487 104029
192429 193787
24289 66737
56456 33117
12406 121250
139510 72340
37754 175679
27730 106773
34512 45901
169159 145205
167199 9455
124988 27796
183030 167303
176967 58418
116279 112701
122931 786...

output:

210281061

result:

ok single line: '210281061'

Test #17:

score: 4
Accepted
time: 158ms
memory: 164052kb

input:

199995 199995 1
74797 7556
81442 135821
185092 167712
42234 63649
134023 46082
134318 22976
128405 107157
36520 80426
167712 198927
132017 118773
288 1341
132649 22081
174449 167712
94580 179706
151008 160583
48868 128462
4161 125098
142488 88139
167712 47267
153225 129410
167712 100469
16050 89116
...

output:

241088863

result:

ok single line: '241088863'

Test #18:

score: 4
Accepted
time: 157ms
memory: 168760kb

input:

199996 25550 1
153865 144748
17792 151663
128934 59764
43644 133644
130769 176056
95288 123429
93190 140114
194626 118534
30624 86065
30624 103291
63137 117845
45411 57110
93790 4225
44261 92925
163904 119841
194626 20904
26921 194626
191171 32365
50763 194808
133250 162111
174639 5106
39176 139051
...

output:

346947170

result:

ok single line: '346947170'

Test #19:

score: 4
Accepted
time: 164ms
memory: 170888kb

input:

200000 24970 9
177589 184389
22449 43171
11368 15434
177589 124467
34715 172282
160344 28685
138184 4137
18031 177589
123360 2900
167503 74776
150552 180476
177589 198321
191168 145709
26761 40657
76252 155219
199611 140454
80426 54961
64064 134456
48347 114493
190498 177589
177589 2360
154689 13729...

output:

659235481

result:

ok single line: '659235481'

Test #20:

score: 4
Accepted
time: 158ms
memory: 167864kb

input:

200000 24973 9
118915 67700
120517 143573
66710 142095
140916 9440
144299 173165
179864 150849
108850 86634
183838 27249
56514 33874
45014 108850
185494 52388
160940 76515
27076 33073
194583 114506
127559 66004
44294 183831
7460 108850
198987 150508
45758 70252
59682 157110
49593 150673
67251 108850...

output:

371741367

result:

ok single line: '371741367'

Test #21:

score: 4
Accepted
time: 174ms
memory: 162912kb

input:

199999 15797 9
111155 118437
116181 103286
171596 117870
169742 58066
37077 12461
115452 191571
126892 134514
115497 151658
189077 76880
28368 17080
186378 14214
62745 18534
142023 76880
150833 175023
26865 15461
49984 107836
92202 136608
184737 112189
86026 148269
76880 147485
101065 111876
39958 1...

output:

923057136

result:

ok single line: '923057136'

Test #22:

score: 4
Accepted
time: 1151ms
memory: 332200kb

input:

999996 144346 1
424407 435560
510418 674573
150671 452726
128147 920948
510027 239220
972006 448279
281095 505374
655082 730449
15872 689268
70185 87349
741472 521817
723804 255286
811374 494975
443017 139873
406268 753301
20508 211500
191993 316128
730092 917846
868622 770478
738161 787331
87502 24...

output:

243642588

result:

ok single line: '243642588'

Test #23:

score: 4
Accepted
time: 1149ms
memory: 345672kb

input:

999997 139853 10
920585 690093
197610 611492
23489 349039
700388 280314
98990 218300
673469 707504
635638 180992
710821 330460
525503 990906
707504 708854
273138 955457
931868 88040
878331 611354
968123 352800
971264 681683
844600 397899
843885 192964
615112 555275
242987 872652
20593 782797
330349 ...

output:

66295209

result:

ok single line: '66295209'

Test #24:

score: 4
Accepted
time: 1118ms
memory: 332928kb

input:

999955 103989 10
925289 178114
308672 659094
669662 430933
561446 607489
799171 728376
452539 684799
9192 983985
974919 329141
696226 20531
172583 956538
197830 414632
820211 684799
180437 882577
684799 945146
18047 421707
266023 709380
377290 420390
920102 395704
702819 208991
700053 332653
479543 ...

output:

296918790

result:

ok single line: '296918790'

Test #25:

score: 4
Accepted
time: 1156ms
memory: 320888kb

input:

999936 123275 9
536599 787920
7994 306084
494368 947491
507729 297675
824018 568122
28934 711706
235386 798753
343255 798753
953136 324491
67553 200106
466356 485763
569760 432140
864787 466356
236533 560892
469895 353561
686792 47275
575895 202643
798753 887888
735885 356054
335977 648100
900249 62...

output:

209607906

result:

ok single line: '209607906'

Extra Test:

score: 0
Extra Test Passed