LibreOJ 3044 「ZJOI2019」Minimax 搜索

发表于 | 分类于 |

注意到 \(w(S)\) 的定义含一个 \(\max\)，于是考虑统计 \(w(S) \le R\) 的个数并差分。

首先如果 \(W \in S\) 显然有 \(w(S) = 1\)，故下文不考虑此情况。

显然，如果要改变 \(W\)，一定是改为 \(W \pm 1\)，并且小于 \(W\) 的一定改为 \(W+1\)，大于 \(W\) 的一定改为 \(W-1\)。
考虑分别求出把某些权值小于 \(W\) 的叶子改为 \(W+1\) 能影响到根或把某些权值大于 \(W\) 的叶子改为 \(W-1\) 能影响到根的方案数，取补集再容斥一下就可以得到答案。

考虑小于 \(W\) 的。
出于方便起见，考虑对概率进行 DP，而不是方案数（是指在当前 \(R\) 限制下有贡献的叶子以 \(\frac 12\) 的概率出现时的总概率）。
设 \(f_u\) 表示使 \(u\) 的权值大于 \(W\) 的概率。
易得 \[ f_u = \begin{cases} 1 - \prod\limits_{v \in {\rm son}(u)}(1 - f_v), & {\rm depth}(u) \equiv 1 \pmod 2 \\ \prod\limits_{v \in {\rm son}(u)} f_v, & {\rm depth}(u) \equiv 0 \pmod 2 \end{cases} \]

这样做起来很麻烦，考虑设 \(F_u = \begin{cases}1 - f_u, & {\rm depth}(u) \equiv 1 \pmod 2 \\ f_u, & {\rm depth}(u) \equiv 0 \pmod 2 \end{cases}\)，则转移变成 \[ F_u = \prod\limits_{v \in {\rm son}(u)} (1 - F_v) \]

大于的类似。
设 \(g_u\) 表示使 \(u\) 的权值小于 \(W\) 的概率。
易得 \[ g_u = \begin{cases} \prod\limits_{v \in {\rm son}(u)} g_v, & {\rm depth}(u) \equiv 1 \pmod 2 \\ 1 - \prod\limits_{v \in {\rm son}(u)}(1 - g_v), & {\rm depth}(u) \equiv 0 \pmod 2 \end{cases} \]

类似地设 \(G_u = \begin{cases}g_u, & {\rm depth}(u) \equiv 1 \pmod 2 \\ 1 - g_u, & {\rm depth}(u) \equiv 0 \pmod 2 \end{cases}\) 即可。

发现每次改变 \(R\) 只会改变一个叶子的贡献，动态 DP 即可。

由于我比较傻，所以我在这里再写一下动态 DP 的细节（
对于小于 \(W\) 的，设 \(F_u\) 表示总 DP 值，\(F'_u\) 表示对轻儿子的 DP 值。
那么转移可以写作 \[ F_u = (1 - F_{ {\rm son}_u }) F'_u = - F'_u \cdot F_{ {\rm son}_u } + F'_u \]

容易发现这是一个一次函数的形式，考虑用线段树维护区间的一次函数复合即可。

调了半年发现我原来还会出数组越界的锅……

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#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]);
}