QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#67461#2578. Minimax 搜索alpha1022100 ✓323ms34980kbC++145.3kb2022-12-10 16:11:072022-12-10 16:11:10

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-10 16:11:10]
  • 评测
  • 测评结果:100
  • 用时:323ms
  • 内存:34980kb
  • [2022-12-10 16:11:07]
  • 提交

answer

#include <cstdio>
#include <utility>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 2e5;
const int mod = 998244353;
const int inv = 499122177;
inline int fpow(int a,int b)
{
    int ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = (long long)ret * a % mod),a = (long long)a * a % mod;
    return ret;
}
int n,L,R;
int to[(N << 1) + 5],pre[(N << 1) + 5],first[N + 5];
inline void add(int u,int v)
{
    static int tot = 0;
    to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
struct Linear
{
    int k,b;
    inline Linear(int x = 1,int y = 0)
    {
        k = x,b = y;
    }
    inline Linear operator*(const Linear &o) const
    {
        return Linear((long long)k * o.k % mod,(b + (long long)k * o.b) % mod);
    }
};
struct node
{
    Linear f,g;
} seg[(N << 2) + 5];
void insert(int x,Linear f,Linear g,int p,int tl,int tr)
{
    if(tl == tr)
    {
        seg[p].f = f,seg[p].g = g;
        return ;
    }
    int mid = tl + tr >> 1;
    x <= mid ? insert(x,f,g,ls,tl,mid) : insert(x,f,g,rs,mid + 1,tr);
    seg[p].f = seg[ls].f * seg[rs].f,
    seg[p].g = seg[ls].g * seg[rs].g;
}
inline pair<Linear,Linear> operator*(const pair<Linear,Linear> &a,const pair<Linear,Linear> &b)
{
    return make_pair(a.first * b.first,a.second * b.second);
}
pair<Linear,Linear> query(int l,int r,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
        return make_pair(seg[p].f,seg[p].g);
    int mid = tl + tr >> 1;
    pair<Linear,Linear> ret;
	ret.first = Linear(),ret.second = Linear();
    l <= mid && (ret = ret * query(l,r,ls,tl,mid),1);
    r > mid && (ret = ret * query(l,r,rs,mid + 1,tr),1);
    return ret;
}
struct Value
{
    int v,cnt;
    inline Value(int x = 0)
    {
        x ? (v = x,cnt = 0) : (v = 1,cnt = 1);
    }
    inline Value(int x,int y)
    {
        v = x,cnt = y;
    }
    inline Value operator*(const Value &o) const
    {
        return Value((long long)v * o.v % mod,cnt + o.cnt);
    }
    inline Value operator/(const Value &o) const
    {
        return Value((long long)v * fpow(o.v,mod - 2) % mod,cnt - o.cnt);
    }
    inline int val()
    {
        return cnt ? 0 : v;
    }
} f[N + 5],g[N + 5];
int F[N + 5],G[N + 5];
int ans[N + 5];
int w[N + 5],W;
int fa[N + 5],dep[N + 5],sz[N + 5],son[N + 5],top[N + 5],id[N + 5],ed[N + 5];
int leaf[N + 5],pw = inv;
void dfs1(int p)
{
    sz[p] = 1;
    if(!(dep[p] & 1))
        w[p] = 0x3f3f3f3f;
    for(register int i = first[p];i;i = pre[i])
        if(to[i] ^ fa[p])
        {
            fa[to[i]] = p,dep[to[i]] = dep[p] + 1,dfs1(to[i]),sz[p] += sz[to[i]];
            if(!son[p] || sz[son[p]] < sz[to[i]])
                son[p] = to[i];
            (dep[p] & 1) ? (w[p] = max(w[p],w[to[i]])) : (w[p] = min(w[p],w[to[i]]));
        }
    if(!son[p])
        leaf[p] = 1,pw = 2LL * pw % mod,w[p] = p;
}
void dfs2(int p)
{
    static int tot = 0;
    id[p] = ++tot,F[p] = G[p] = 1,f[p] = g[p] = Value(1);
    if(son[p])
        top[son[p]] = top[p],dfs2(son[p]),ed[p] = ed[son[p]],
        F[p] = (long long)F[p] * (1 - F[son[p]] + mod) % mod,
        G[p] = (long long)G[p] * (1 - G[son[p]] + mod) % mod;
    else
        ed[p] = p,
        F[p] = p > W,G[p] = p < W,
        (dep[p] & 1) ? (F[p] = (1 - F[p] + mod) % mod) : (G[p] = (1 - G[p] + mod) % mod),
        f[p] = Value(F[p]),g[p] = Value(G[p]);
    for(register int i = first[p];i;i = pre[i])
        if(!id[to[i]])
            top[to[i]] = to[i],dfs2(to[i]),
            F[p] = (long long)F[p] * (1 - F[to[i]] + mod) % mod,
            G[p] = (long long)G[p] * (1 - G[to[i]] + mod) % mod,
            f[p] = f[p] * Value((1 - F[to[i]] + mod) % mod),
            g[p] = g[p] * Value((1 - G[to[i]] + mod) % mod);
}
void update(int x)
{
    for(;x;x = fa[x])
    {
        insert(id[x],Linear((mod - f[x].val()) % mod,f[x].val()),Linear((mod - g[x].val()) % mod,g[x].val()),1,1,n),x = top[x];
        pair<Linear,Linear> cur = query(id[x],id[ed[x]],1,1,n);
        if(fa[x])
            f[fa[x]] = f[fa[x]] / Value((1 - F[x] + mod) % mod),
            g[fa[x]] = g[fa[x]] / Value((1 - G[x] + mod) % mod);
        F[x] = cur.first.b,G[x] = cur.second.b;
        if(fa[x])
            f[fa[x]] = f[fa[x]] * Value((1 - F[x] + mod) % mod),
            g[fa[x]] = g[fa[x]] * Value((1 - G[x] + mod) % mod);
    }
}
int main()
{
    scanf("%d%d%d",&n,&L,&R);
    int u,v;
    for(register int i = 2;i <= n;++i)
        scanf("%d%d",&u,&v),add(u,v),add(v,u);
    dep[1] = top[1] = 1,dfs1(1),W = w[1],dfs2(1);
    for(register int i = 1;i <= n;++i)
        insert(id[i],Linear((mod - f[i].val()) % mod,f[i].val()),Linear((mod - g[i].val()) % mod,g[i].val()),1,1,n);
    for(register int i = 2;i < n;++i)
    {
        if(W - i + 1 > 0 && leaf[W - i + 1])
            f[W - i + 1] = Value(inv),update(W - i + 1);
        if(W + i - 1 <= n && leaf[W + i - 1])
            g[W + i - 1] = Value(inv),update(W + i - 1);
        ans[i] = (1 - (long long)F[1] * (1 - G[1] + mod) % mod + mod) * pw % mod;
    }
    ans[n] = pw - 1;
    for(register int i = 1;i <= n;++i)
        ans[i] = (ans[i] + pw) % mod;
    for(register int i = n;i;--i)
        ans[i] = (ans[i] - ans[i - 1] + mod) % mod;
    for(register int i = L;i <= R;++i)
        printf("%d%c",ans[i]," \n"[i == R]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 1ms
memory: 17284kb

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: 1ms
memory: 17280kb

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: 17136kb

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: 11ms
memory: 17612kb

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: 5ms
memory: 17480kb

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: 289ms
memory: 34976kb

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: 279ms
memory: 34956kb

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: 311ms
memory: 34956kb

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: 305ms
memory: 34964kb

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: 323ms
memory: 34980kb

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