QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#288641 | #2578. Minimax 搜索 | yhk1001 | 100 ✓ | 239ms | 37796kb | C++14 | 5.1kb | 2023-12-23 08:58:14 | 2023-12-23 08:58:14 |
Judging History
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