QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#288641#2578. Minimax 搜索yhk1001100 ✓239ms37796kbC++145.1kb2023-12-23 08:58:142023-12-23 08:58:14

Judging History

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

  • [2023-12-23 08:58:14]
  • 评测
  • 测评结果:100
  • 用时:239ms
  • 内存:37796kb
  • [2023-12-23 08:58:14]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2e5, E = N << 1, SZ = N << 2;
const long long P = 998244353, Inv2 = (P + 1) >> 1;

int n, Left, Right, W;
long long ans[N + 5];

int head[N + 5], to[E + 5], nxt[E + 5], tot = 1;
void add_edge(int u, int v)
{
	tot++;
	to[tot] = v;
	nxt[tot] = head[u];
	head[u] = tot;
	return ;
}
void add(int u, int v)
{
	add_edge(u, v);
	add_edge(v, u);
	return ;
}

long long ksm(long long d, long long u)
{
	long long res = 1;
	while (u)
	{
		if (u & 1)
			res = res * d % P;
		u >>= 1;
		d = d * d % P;
	}
	return res;
}

struct Integer
{
	long long val;
	int zero;

	Integer()
	{
		val = 1, zero = 0;
	}
	void multiply(long long x)
	{
		if (!x)
			zero++;
		else
			val = val * x % P;
		return ;
	}
	void divide(long long x)
	{
		if (!x)
			zero--;
		else
			val = val * ksm(x, P - 2) % P;
		return ;
	}
	long long get()
	{
		return (!zero) * val;
	}
};

struct Function
{
	long long k, b;

	Function operator * (const Function& fun) const
	{
		return Function{k * fun.k % P, (b * fun.k % P + fun.b) % P};
	}
};

struct SegmentTree
{
	Function fun[SZ + 5];

	#define ls(p) (p << 1)
	#define rs(p) (p << 1 | 1)

	void pushup(int p)
	{
		fun[p] = fun[rs(p)] * fun[ls(p)];
		return ;
	}
	void modify(int p, int l, int r, int pos, Function func)
	{
		if (l == r)
			return fun[p] = func, void();
		int mid = (l + r) >> 1;
		if (pos <= mid)
			modify(ls(p), l, mid, pos, func);
		else
			modify(rs(p), mid + 1, r, pos, func);
		pushup(p);
		return ;
	}
	Function query(int p, int l, int r, int L, int R)
	{
		if (L <= l && r <= R)
			return fun[p];
		int mid = (l + r) >> 1;
		if (R <= mid)
			return query(ls(p), l, mid, L, R);
		if (L > mid)
			return query(rs(p), mid + 1, r, L, R);
		return query(rs(p), mid + 1, r, L, R) * query(ls(p), l, mid, L, R);
	}
} tree;

int w[N + 5], opt[N + 5];//whether changing is better
long long s[N + 5];//subsets

int fa[N + 5], dep[N + 5], sz[N + 5], son[N + 5];
int dfn[N + 5], top[N + 5], tail[N + 5], tim;

Integer dp[N + 5];//light son, init = 1, dep = 1, dp = >W; dep = 0, dp = <W
long long Dp[N + 5];//all son

void dfs0(int u, int father, int depth)
{
	fa[u] = father, dep[u] = depth, sz[u] = 1;
	w[u] = (!depth) * n, s[u] = 1;

	for (int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if (v == father)
			continue;

		dfs0(v, u, !depth);
		s[u] = s[u] * s[v] % P;
		sz[u] += sz[v];

		if (depth)
			w[u] = max(w[u], w[v]);
		else
			w[u] = min(w[u], w[v]);
	}

	if (sz[u] == 1)
		w[u] = u, s[u] = 2;
	return ;
}
void dfs1(int u)
{
	for (int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if (v == fa[u])
			continue;

		dfs1(v);
		if (w[u] == W)
		{
			if (w[v] == W)
				son[u] = v;
			continue;
		}
		if (!son[u] || sz[son[u]] < sz[v])
			son[u] = v;
	}
	return ;
}
int dfs2(int u, int tp, int deplca)
{
	dfn[u] = ++tim, top[u] = tp;

	opt[u] = deplca ^ (u > W);//1, u < W; 0, u > W
	if (w[u] == W)
		deplca = dep[u];

	tail[u] = u;//leaf
	if (son[u])
		tail[u] = dfs2(son[u], tp, deplca);

	for (int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		if (v == fa[u] || v == son[u])
			continue;

		dfs2(v, v, deplca);
		dp[u].multiply(Dp[v]);
	}
	Dp[u] = (s[u] - dp[u].get() * Dp[son[u]] % P + P) % P;

	Function func;
	if (u == W)
		func = Function{0, 1};
	else if (sz[u] == 1)//leaf
	{
		func = Function{0, ((u < W) ^ dep[u]) * 2};
		Dp[u] = func.b;
	}
	else if (w[u] == W)//on chain or W
		func = Function{dp[u].get(), 0};
	else
		func = Function{(P - dp[u].get()) % P, s[u]};

	tree.modify(1, 1, n, dfn[u], func);
	return tail[u];
}

void update(int u)
{
	Function func;

	int p = u;
	while (w[p] != W)//delete
	{
		int tp = top[p], anc = fa[tp];
		func = tree.query(1, 1, n, dfn[tp], dfn[tail[tp]]);
		dp[anc].divide(func.b);
		p = anc;
	}
	tree.modify(1, 1, n, dfn[u], Function{0, 1});//f = g = 1

	p = u;
	while (w[p] != W)//add
	{
		int tp = top[p], anc = fa[tp];
		func = tree.query(1, 1, n, dfn[tp], dfn[tail[tp]]);
		
		dp[anc].multiply(func.b);
		if (w[anc] == W)
			func = Function{dp[anc].get(), 0};
		else
			func = Function{(P - dp[anc].get()) % P, s[anc]};

		tree.modify(1, 1, n, dfn[anc], func);
		p = anc;
	}
	return ;
}

int main()
{
	// freopen("minimax.in", "r", stdin);
	// freopen("minimax.out", "w", stdout);

	scanf("%d%d%d", &n, &Left, &Right);
	for (int i = 1, u, v; i < n; i++)
	{
		scanf("%d%d", &u, &v);
		add(u, v);
	}

	dfs0(1, 0, 1);
	W = w[1];
	dfs1(1);
	dfs2(1, 1, 0);

	ans[1] = s[1] * Inv2 % P;
	for (int k = 2; k < n; k++)
	{
		if (W - k + 1 > 0 && sz[W - k + 1] == 1 && opt[W - k + 1])//lca: max, top: min
			update(W - k + 1);

		if (W + k - 1 <= n && sz[W + k - 1] == 1 && opt[W + k - 1])//lca: min, top: max
			update(W + k - 1);

		ans[k] = (s[1] + P - tree.query(1, 1, n, 1, tail[1]).b) % P;
	}
	ans[n] = (s[1] + P - 1) % P;

	for (int k = Left; k <= Right; k++)
		printf("%lld ", (ans[k] + P - ans[k - 1]) % P);
	printf("\n");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 0ms
memory: 18284kb

input:

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

output:

27 

result:

ok 1 number(s): "27"

Test #2:

score: 10
Accepted
time: 0ms
memory: 20328kb

input:

50 50 50
8 6
4 29
11 9
6 31
6 37
6 40
3 2
24 23
24 10
38 29
5 11
18 22
14 18
3 22
6 50
2 39
21 28
35 6
25 6
7 1
42 6
6 48
2 1
29 45
33 45
6 5
4 5
6 13
15 6
6 36
34 38
43 6
17 19
45 41
30 6
6 16
46 6
4 3
22 23
6 49
27 6
6 32
19 7
12 7
6 26
6 47
24 20
18 21
6 44

output:

268435455 

result:

ok 1 number(s): "268435455"

Test #3:

score: 10
Accepted
time: 0ms
memory: 22356kb

input:

50 50 50
42 50
16 6
45 29
11 20
31 6
6 36
6 38
4 3
42 4
1 2
14 12
23 17
7 22
37 42
7 8
6 13
3 8
45 42
34 6
6 27
9 10
39 6
48 6
3 2
14 5
14 23
9 1
6 5
19 6
25 6
6 35
12 18
40 6
32 2
11 18
30 6
26 6
44 6
4 5
15 22
49 6
47 42
6 33
9 21
32 41
28 6
6 46
8 24
43 6

output:

94371839 

result:

ok 1 number(s): "94371839"

Test #4:

score: 10
Accepted
time: 7ms
memory: 22368kb

input:

5000 5000 5000
3391 4162
1887 100
4806 2707
3384 4352
360 1060
4138 4214
1779 1103
2745 100
3191 2839
1054 815
100 3050
2140 821
2298 2006
4839 2857
4799 3088
4389 4821
100 1218
4538 2668
3948 100
437 759
4958 2943
100 2929
1016 100
4514 2626
3211 4464
4412 100
100 4290
3754 3464
317 139
3543 4038
1...

output:

290613167 

result:

ok 1 number(s): "290613167"

Test #5:

score: 10
Accepted
time: 0ms
memory: 18328kb

input:

5000 5000 5000
4416 4742
3447 100
100 2139
2595 100
2730 100
2149 100
4132 4652
100 920
1171 93
4466 100
100 3056
1560 2330
980 100
4579 3690
4534 3402
3704 3658
100 4930
100 2544
4731 3198
346 2059
100 4645
261 2135
1496 2110
2796 4020
4152 3963
202 1395
100 4476
2664 100
292 100
100 1848
670 1093
...

output:

672429329 

result:

ok 1 number(s): "672429329"

Test #6:

score: 10
Accepted
time: 200ms
memory: 37796kb

input:

200000 64514 64564
166899 160082
60000 64526
33102 33103
85144 46777
2004 2005
60000 112699
54273 60449
186175 58944
38006 38007
57273 57274
60000 103775
60000 155227
141800 17902
101772 60000
29188 29187
199105 60000
77650 62888
197631 15538
60000 125137
13692 13693
17616 17617
81823 27527
121752 9...

output:

0 12553453 0 0 505398903 0 0 751821628 375910814 0 0 781055287 296549940 0 148274970 0 0 74137485 767217636 0 0 0 0 0 0 152582101 786828790 0 0 181998832 0 0 136499124 22749854 0 0 0 0 11374927 0 0 504809640 252404820 0 0 0 189303615 530672779 764458566 0 0 

result:

ok 51 numbers

Test #7:

score: 10
Accepted
time: 229ms
memory: 37756kb

input:

200000 56869 56919
17597 17596
178411 181603
103240 63527
111797 38549
85990 117256
6726 6725
48441 48442
55270 177787
15041 15040
16877 16878
39504 185195
89404 38539
36826 36827
190491 60000
36740 36741
88429 60000
14220 14221
960 961
17416 17415
60000 170695
60000 94416
60000 186798
43121 63148
9...

output:

0 0 0 0 305716403 325990189 494053730 0 612498716 0 0 0 0 434831237 0 857391074 0 287842258 143921129 0 0 0 571082741 0 784663547 0 0 0 891453950 0 0 445726975 0 0 721985664 360992832 0 0 0 180496416 0 90248208 0 0 0 0 0 45124104 22562052 0 11281026 

result:

ok 51 numbers

Test #8:

score: 10
Accepted
time: 239ms
memory: 37676kb

input:

200000 1 200000
184410 36878
13415 107366
68975 107143
106233 47847
16430 16429
191196 60000
46312 195146
41972 41971
20134 20133
164221 60000
194109 12132
60000 107792
60000 195701
7233 7232
35452 138684
41288 41287
13034 13035
43109 68299
178092 60000
29369 29368
137533 60000
60000 104755
97630 60...

output:

208949170 104474585 0 0 0 551359469 0 0 0 0 774801911 0 886523132 0 0 0 443261566 221630783 609937568 0 0 304968784 0 0 152484392 0 0 0 0 0 0 76242196 0 38121098 0 0 0 0 0 0 19060549 508652451 0 0 0 0 0 753448402 376724201 0 687484277 842864315 0 0 0 0 0 0 0 0 920554334 460277167 0 0 0 0 0 729260760...

result:

ok 200000 numbers

Test #9:

score: 10
Accepted
time: 235ms
memory: 35760kb

input:

200000 1 200000
60000 177996
29350 29351
60000 137658
60000 104670
60000 97458
6864 6863
87382 119869
82861 55561
60000 120168
10383 115806
15616 169696
112943 60000
54306 54307
60000 88032
181816 60000
60284 115176
178527 18228
85284 70160
69368 60000
82772 60000
4197 4198
101756 60000
60000 124381...

output:

7773226 0 0 0 3886613 0 501065483 0 749654918 0 0 374827459 0 0 0 31559506 670756153 834500253 0 0 0 0 0 0 916372303 957308328 0 0 0 478654164 239327082 119663541 0 558953947 169654372 0 0 0 0 0 0 693771964 346885982 0 173442991 585843672 0 292921836 0 0 0 0 0 0 0 146460918 0 73230459 0 0 0 53573740...

result:

ok 200000 numbers

Test #10:

score: 10
Accepted
time: 233ms
memory: 37736kb

input:

200000 1 200000
126513 83099
5686 5685
190737 50666
60000 175645
45263 45264
64096 60000
60000 88117
26201 26200
50979 50978
166070 43900
6611 72182
168284 60000
13093 69143
8233 120546
60000 125398
22942 22941
143390 144759
33279 128246
19415 19416
60000 74434
167203 60000
36776 191353
17351 17352
...

output:

330236643 0 0 0 0 0 0 0 664240498 332120249 0 0 0 665182301 0 0 831713327 0 914978840 0 0 0 0 0 0 457489420 0 0 0 0 0 0 228744710 0 0 114372355 0 556308354 0 278154177 0 638199265 818221809 0 0 908233081 0 953238717 0 975741535 0 0 986992944 0 0 0 740244708 0 0 0 0 123374118 61687059 0 0 0 794948559...

result:

ok 200000 numbers

Extra Test:

score: 0
Extra Test Passed