题解 P5281 【[ZJOI2019]Minimax搜索】
Owen_codeisking
2019-04-03 15:34:55
$\%\%\% lyx$ 考场切 $T_3$
我来口胡一个假的 $O(n\log n)$ 解法。
一些废话：我考前奶 $noip$ 有动态 $dp$ 那么 $ZJOI$ 也有一道动态 $dp$，结果奶中了。
### 前置知识：动态 $dp$
最好是用全局平衡二叉树，用其他的也可以，时限不卡。
现在我们要挖掘根结点的值改变和函数 $w(S)$ 有什么特殊的性质。
### 1、$W$ 在变化成 $W\pm k$ 的形式时一定能变化成 $W\pm 1$
显然，我们可以在 $O(n)$ 时间内求出当前的 $W$
我们发现递推式：
$$\begin{cases}w_i=\text{min}_{fa_j=i}\ w_j&dep_i\ \text{mod}\ 2=0,i\notin leaf\\w_i=\text{max}_{fa_j=i}\ w_j&dep_i\ \text{mod}\ 2=1,i\notin leaf\\w_i=i&i\in leaf\end{cases}$$
可知 $w_i$ 一定取自叶子结点的编号。对于一个集合 $S$，我们验证是否存在 $w(S)=k$ 等价于把当前所有 $|T|=k$ 子集的元素改成 $W\pm1$ 跑一遍 $O(n)$ 的树形 $dp$
### 2、$w(S)\leq k$ 等价于 $w({x|x\in S,x<W})\leq k$ 或 $w({x|x\in S,x>W})\leq k$
其实就是把 $x>W$ 的叶子结点改成 $W-1$，$x<W$ 的叶子结点改成 $W+1$ 然后判合法。
### 3、转化询问形式
我们可以把答案差分一下，求 $w(S)\leq k$ 的方案数。方案数如果不好合并，那么转化成概率。$[L,R]$ 这个区间只是为了给部分分用的。
### 4、开始 $dp$
$x<W$ 和 $x>W$ 的 $dp$ 是类似的，所以我们只要讨论一种情况。
$f_i$ 表示在 $i$ 的权值 $<W$ 的概率。
$$f'_i=\prod_{fa_j=i}(1-f'_j)$$
$$f'_i=[i\ \text{mod}\ 2=0]f_i+[i\ \text{mod}\ 2=1](1-f_i)$$
这两条式子可以去掉深度奇偶性的分类，具体推导可以感性理解一下。
接下来就是从小到大枚举并修改每个叶子结点的概率，这部分可以用动态 $dp$ 实现。
但是有一个问题，每一次我们要重新除以 $1-f'_j$，就无法避免 $1-f'_j$ 为 $0$ 的情况。那么我们还要再写一个 $data$ 结构体，人工排除这种情况。
由于每次我们都要求 $1-f'_j$ 的逆元，所以理论上还有一个 $\log$ 的。我问了一下 $kczno1$，这个解法可以被完全可以被完全二叉树卡到 $O(n\log^2 n)$
$Code\ Below:$
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200000+10;
const int mod=998244353;
int n,L,R,head[maxn],to[maxn<<1],nxt[maxn<<1],tot;
int m,W,w[maxn],top[maxn],dep[maxn],siz[maxn],son[maxn],fa[maxn];ll ans[maxn];
inline int read()
{
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
void print(ll x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
inline ll fpow(ll a,ll b)
{
ll ret=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) ret=ret*a%mod;
return ret;
}
inline void addedge(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int f)
{
siz[x]=1;fa[x]=f;dep[x]=dep[f]+1;
int maxson=-1;
for(int i=head[x],y;i;i=nxt[i])
{
y=to[i];
if(y==f) continue;
dfs(y,x);siz[x]+=siz[y];
if(siz[y]>maxson) son[x]=y,maxson=siz[y];
}
if(!son[x]) w[x]=x;
else
{
w[x]=w[son[x]];
for(int i=head[x],y;i;i=nxt[i])
{
y=to[i];
if(y==f||y==son[x]) continue;
if(dep[x]&1) w[x]=max(w[x],w[y]);
else w[x]=min(w[x],w[y]);
}
}
}
struct data
{
ll x;int now;
inline void operator *= (const ll &b)
{
if(!b) now++;
else x=x*b%mod;
}
inline void operator /= (const ll &b)
{
if(!b) now--;
else x=x*fpow(b,mod-2)%mod;
}
inline operator ll()
{
return now?0:x;
}
};
struct node
{
ll x,y;
inline operator ll()
{
return y;
}
};
inline node operator + (const node &a,const node &b)
{
return (node){a.x*b.x%mod,(a.y+a.x*b.y)%mod};
}
struct Global_bst
{
int rt,ch[maxn][2],fa[maxn],sta[maxn],top;bool nrt[maxn],d;
node sum[maxn];data dp[maxn];
inline void pushup(int x)
{
sum[x]=(node){-dp[x],dp[x]};
if(ch[x][0]) sum[x]=sum[ch[x][0]]+sum[x];
if(ch[x][1]) sum[x]=sum[x]+sum[ch[x][1]];
}
int build(int l,int r)
{
if(l>r) return 0;
int sum=0,now=0,x;
for(int i=l;i<=r;i++) sum+=siz[sta[i]]-siz[son[sta[i]]];
for(int i=l;i<=r;i++)
{
now+=siz[sta[i]]-siz[son[sta[i]]];
if((now<<1)>=sum)
{
x=sta[i];
if(!son[x])
{
if(d==0) dp[x].x=(x<W);
else dp[x].x=1-(x>W);
if(!(dep[x]&1)) dp[x].x=1-dp[x].x;
}
fa[ch[x][0]=build(l,i-1)]=x;
fa[ch[x][1]=build(i+1,r)]=x;
pushup(x);return x;
}
}
}
int dfs(int topf,int f)
{
for(int x=topf;x;f=x,x=son[x])
{
dp[x].x=1;
for(int i=head[x],y,z;i;i=nxt[i])
{
y=to[i];
if(y==f||y==son[x]) continue;
z=dfs(y,x);fa[z]=x;dp[x]*=1-sum[z];
}
}
top=0;
for(int x=topf;x;x=son[x]) sta[++top]=x;
return build(1,top);
}
inline void init()
{
rt=dfs(1,0);
for(int x=1;x<=n;x++)
{
if(ch[fa[x]][0]==x||ch[fa[x]][1]==x) nrt[x]=1;
else nrt[x]=0;
}
}
inline void modify(int x,ll y)
{
if(!(dep[x]&1)) y=1-y;
dp[x].x=y;dp[x].now=0;
while(x)
{
if(!nrt[x])
{
dp[fa[x]]/=1-sum[x];
pushup(x);
dp[fa[x]]*=1-sum[x];
}
else pushup(x);
x=fa[x];
}
}
inline ll get()
{
return sum[rt];
}
}T[2];
int main()
{
n=read(),L=read(),R=read();
int x,y;
for(int i=1;i<n;i++)
{
x=read(),y=read();
addedge(x,y),addedge(y,x);
}
dfs(1,0);W=w[1];
for(int x=1;x<=n;x++)
if(x!=son[fa[x]])
for(int y=x;y;y=son[y]) top[y]=x;
for(int x=1;x<=n;x++) m+=!son[x];
ll now=fpow(2,m-1),inv2=(mod+1)>>1;
T[0].d=0;T[1].d=1;T[0].init();T[1].init();
for(int i=1;i<n;i++)
{
x=W+i-1;
if(x>W&&x<=n&&!son[x]) T[0].modify(x,inv2);
x=W-i+1;
if(x>0&&x<W&&!son[x]) T[1].modify(x,inv2);
ans[i]=now*(2-(1-T[0].get())*T[1].get()%mod)%mod;
}
ans[n]=now*2-1;
for(int i=L;i<=R;i++) print(((ans[i]-ans[i-1])%mod+mod)%mod),putchar(' ');
putchar('\n');
return 0;
}
```