Loj #3044. 「ZJOI2019」Minimax 搜索
题目描述
九条可怜是一个喜欢玩游戏的女孩子。为了增强自己的游戏水平，她想要用理论的武器武装自己。这道题和著名的 Minimax 搜索有关。
可怜有一棵有根树，根节点编号为 \(1\)。定义根节点的深度为 \(1\)，其他节点的深度为它的父亲的深度加一。同时在叶子节点权值给定的情况下，可怜用如下方式定义了每一个非节点的权值：
- 对于深度为奇数的非叶子节点，它的权值是它所有子节点的权值最大值。
- 对于深度为偶数的非叶子节点，它的权值是它所有子节点的权值最小值。
最开始，可怜令编号为 \(i\) 的叶子节点权值为 \(i\)，并计算得到了根节点的权值为 \(W\)。
现在，邪恶的 Cedyks 想要通过修改某些叶子节点的权值，来让根节点的权值发生改变。Cedyks 设计了一个量子攻击器，在攻击器发动后，Cedyks 会随机获得一个非空的叶子节点集合 \(S\) 的控制权，并可以花费一定的能量来修改 \(S\) 中的叶子节点的权值。
然而，修改叶子节点的权值也要消耗能量，对于 \(S\) 中的叶子节点 \(i\)，它的初始权值为 \(i\)，假设 Cedyks 把它的权值修改成了 \(w_i\)（\(w_i\) 可以是任意整数，包括负数），则 Cedyks 在这次攻击中，需要花费的能量为 \(\max_{i\in S} |i − w_i|\)。
Cedyks 想要尽可能节约能量，于是他总是会*以最少的能量来完成攻击*，即在花费的能量最小的情况下，让根节点的权值发生改变。令 \(w(S)\) 为 Cedyks 在获得了集合 \(S\) 的控制权后，会花费的能量。特殊地，对于某些集合 \(S\)，可能无论如何改变 \(S\) 中叶子节点的权值，根节点的权值都不会发生改变，这时，\(w(S)\) 的值被定义为 \(n\)。为了方便，我们称 \(w(S)\) 为 \(S\) 的稳定度。
当有 \(m\) 个叶子节点的时候，一共有 \(2^m − 1\) 种不同的叶子节点的非空集合。在发动攻击前，Cedyks 想要先预估一下自己需要花费的能量。于是他给出了一个区间 \([L, R]\)，他想要知道对于每一个 \(k \in [L, R]\)，有多少个集合 \(S\) 满足 \(w(S) = k\)。
输入格式
第一行输入三个整数 \(n, L, R(n \ge 2, 1 \le L \le R \le n)\)。
接下来 \(n − 1\) 行每行两个整数 \(u, v\)，表示树上的一条边。
输出格式
输出一行 \(R − L + 1\) 个整数，第 \(i\) 个整数表示 \(w(S)\) 为 \(L + i − 1\) 的集合 \(S\) 有多少个。答案可能会很大，请对 \(998244353\) 取模后输出。
数据范围与提示
对于 \(100\%\) 的数据，保证 \(2\leq n \leq 10^5, 1 \le L \le R \le n\)。
\(\\\)
首先考虑\(70\)分的暴力：
考虑先求答案的前缀和再差分，即求稳定度\(\leq k\)的集合数量，记为\(ans_k\)。设\(1\)号点最终的权值是\(W\)。那么其他的点要改变的话要么为\(W+1\)，要么为\(W-1\)。设\(leaf_i\)表示第\(i\)个点为根的子树中叶子节点的个数。
我们发现\(ans_1=2^{leaf_1-1}\)，也就是该集合必须包含\(W\)，其他的点任意。然后对于\(k>1\)，我们求答案的反面，也就是使得最终\(1\)号点的权值不变的集合数量。我们先将\(1\)到\(W\)这条链上单独提出来，然后对于一个深度为奇数的点，我们要令它的所有不在这条链上的叶子节点的权值都\(\leq W\)，反正则必须都\(\geq W\)。这个可以用树形\(DP\)解决。
以\(\leq W\)为例。设\(f_v\)表示使得\(v\)的权值\(\leq W\)的方案数，转移的时候按度数讨论：
- 度数为奇数：\(f_v=\prod_{u\in son_v}f_u\)。
- 度数为偶数：\(f_v=2^{leaf_v}-\prod_{u\in Son_v}(2^{leaf_u}-f_u)\)
第二类情况就是先算答案的反面在求正面。
然后考虑\(v\)是叶子的情况：\(f_v=[v\leq W]+[v+k\leq W]\)。前一个是不选\(v\)，后一个是选了\(v\)。
复杂度时\(O(n*(R-L+1))\)。
正解的话发现每次\(k+1\)后最多两个叶子的权值发生了变化，用动态\(DP\)维护就好了。
具体细节还是有点多，首先将\(1\)到\(W\)这条链上的其他子树进行树剖，然后\(\leq W\)和\(\geq W\)要分别维护。维护的是概率，方便转移。对于每个点，我们要维护其虚儿子的：
G_v=\prod_{u}(1-f_u)
\]
转移矩阵的话也奇偶讨论一下。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
const ll mod=998244353;
ll ksm(ll t,ll x) {
ll ans=1;
for(;x;x>>=1,t=t*t%mod)
if(x&1) ans=ans*t%mod;
return ans;
}
struct info {
ll a,z;
info() {a=1,z=0;}
info(ll _a,ll _z) {a=_a,z=_z;}
ll val() {return z?0:a;}
};
info operator *(const info &x,const info &y) {return info(x.a*y.a%mod,x.z+y.z);}
info operator /(const info &x,const info &y) {return info(x.a*ksm(y.a,mod-2)%mod,x.z-y.z);}
info operator *(info x,ll y) {
if(y==mod) y=0;
if(y) x.a=x.a*y%mod;
else x.z++;
return x;
}
info operator /(info x,ll y) {
if(y==mod) y=0;
if(y) x.a=x.a*ksm(y,mod-2)%mod;
else x.z--;
return x;
}
struct matrix {
ll a[4];
matrix() {memset(a,0,sizeof(a));}
};
matrix operator *(const matrix &x,const matrix &y) {
matrix z;
z.a[0]=(x.a[0]*y.a[0])%mod;
z.a[1]=(x.a[0]*y.a[1])%mod;
z.a[2]=(x.a[2]*y.a[0]+y.a[2])%mod;
z.a[3]=(x.a[2]*y.a[1]+y.a[3])%mod;
return z;
}
const ll inv2=mod+1>>1;
int n,L,R;
int val[N];
bool leaf[N];
int size[N];
ll pw[N];
struct road {int to,nxt;}s[N<<1];
int h[N],cnt;
void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}
int fa[N];
int dep[N];
int son[N],SIZE[N];
bool key[N];
void dfs(int v,int fr) {
int flag=0;
if(dep[v]&1) val[v]=0;
else val[v]=1e9;
SIZE[v]=1;
for(int i=h[v];i;i=s[i].nxt) {
int to=s[i].to;
if(to==fr) continue ;
dep[to]=dep[v]+1;
flag=1;
dfs(to,v);
SIZE[v]+=SIZE[to];
if(SIZE[son[v]]<SIZE[to]) son[v]=to;
fa[to]=v;
size[v]+=size[to];
if(dep[v]&1) val[v]=max(val[v],val[to]);
else val[v]=min(val[v],val[to]);
}
if(!flag) {
size[v]=1;
leaf[v]=1;
val[v]=v;
}
}
int dfn[N],lst[N],id;
int top[N],bot[N];
struct ST {
int flag;
info F[N],G[N];
struct tree {
int l,r;
matrix st;
}tr[N<<2];
void update(int v) {tr[v].st=tr[v<<1|1].st*tr[v<<1].st;}
void build(int v,int l,int r) {
tr[v].l=l,tr[v].r=r;
if(l==r) return ;
int mid=l+r>>1;
build(v<<1,l,mid),build(v<<1|1,mid+1,r);
}
void Modify(int v,int p) {
if(tr[v].l>p||tr[v].r<p) return ;
if(tr[v].l==tr[v].r) {
int now=lst[p];
memset(tr[v].st.a,0,sizeof(tr[v].st.a));
ll *a=tr[v].st.a;
if((dep[now]&1)==flag) {
a[0]=F[now].val();
a[1]=(mod-G[now].val())%mod;
a[3]=G[now].val();
} else {
a[0]=G[now].val();
a[1]=(mod-G[now].val())%mod;
a[2]=(mod+1-G[now].val())%mod;
a[3]=G[now].val();
}
return ;
}
Modify(v<<1,p),Modify(v<<1|1,p);
update(v);
}
matrix query(int v,int l,int r) {
if(l<=tr[v].l&&tr[v].r<=r) return tr[v].st;
int mid=tr[v].l+tr[v].r>>1;
if(r<=mid) return query(v<<1,l,r);
else if(l>mid) return query(v<<1|1,l,r);
else return query(v<<1|1,l,r)*query(v<<1,l,r);
}
ll query(int v) {
if(v==bot[v]) {
return F[v].val();
} else {
ll f=F[bot[v]].val();
matrix tem=query(1,dfn[v],dfn[bot[v]]-1);
return (f*tem.a[0]+tem.a[2])%mod;
}
}
void Change(int v,int f) {
for(int i=top[v];!key[fa[i]];i=top[fa[i]]) {
ll f=query(i);
F[fa[i]]=F[fa[i]]/f;
G[fa[i]]=G[fa[i]]/(mod+1-f);
}
F[v]=info(1,0)*f;
Modify(1,dfn[v]);
for(int i=top[v];!key[fa[i]];i=top[fa[i]]) {
ll f=query(i);
F[fa[i]]=F[fa[i]]*f;
G[fa[i]]=G[fa[i]]*(mod+1-f);
Modify(1,dfn[fa[i]]);
}
}
}Mn,Mx;
int Find_top(int v) {
v=top[v];
while(!key[fa[v]]) v=top[fa[v]];
return v;
}
info now;
void Div(int v,int tp) {
dfn[v]=++id;
lst[id]=v;
top[v]=tp;
bot[v]=v;
if(son[v]) {
Div(son[v],tp);
bot[v]=bot[son[v]];
}
for(int i=h[v];i;i=s[i].nxt) {
int to=s[i].to;
if(to==fa[v]||to==son[v]) continue ;
Div(to,to);
ll fmx=Mx.query(to),fmn=Mn.query(to);
Mx.F[v]=Mx.F[v]*fmx;
Mx.G[v]=Mx.G[v]*(mod+1-fmx);
Mn.F[v]=Mn.F[v]*fmn;
Mn.G[v]=Mn.G[v]*(mod+1-fmn);
}
if(leaf[v]) {
ll mx=((val[v]<=val[1])+(val[v]+2<=val[1]))*inv2%mod;
Mx.F[v]=Mx.F[v]*mx;
ll mn=((val[v]>=val[1])+(val[v]-2>=val[1]))*inv2%mod;
Mn.F[v]=Mn.F[v]*mn;
}
Mx.Modify(1,dfn[v]);
Mn.Modify(1,dfn[v]);
}
void dfs2(int v) {
key[v]=1;
for(int i=h[v];i;i=s[i].nxt) {
int to=s[i].to;
if(to==fa[v]) continue ;
if(val[to]==val[v]) dfs2(to);
else {
Div(to,to);
if(dep[v]&1) {
now=now*Mx.query(to);
} else {
now=now*Mn.query(to);
}
}
}
}
ll ans[N];
int main() {
n=Get(),L=Get(),R=Get();
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2%mod;
for(int i=1;i<n;i++) {
int a=Get(),b=Get();
add(a,b),add(b,a);
}
dep[1]=1;
dfs(1,0);
Mx.flag=1;
Mx.build(1,1,n);
Mn.build(1,1,n);
dfs2(1);
ans[1]=inv2;
ans[2]=((1+mod-now.val())*inv2+inv2)%mod;
ans[n]=1;
for(int i=3;i<n;i++) {
int x=val[1]-i+1,y=val[1]+i-1;
if(x>0&&leaf[x]&&!key[x]) {
int tp=Find_top(x);
if(dep[tp]&1) now=now/Mn.query(tp);
else now=now/Mx.query(tp);
Mx.Change(x,inv2);
if(dep[tp]&1) now=now*Mn.query(tp);
else now=now*Mx.query(tp);
}
if(y<=n&&leaf[y]&&!key[y]) {
int tp=Find_top(y);
if(dep[tp]&1) now=now/Mn.query(tp);
else now=now/Mx.query(tp);
Mn.Change(y,inv2);
if(dep[tp]&1) now=now*Mn.query(tp);
else now=now*Mx.query(tp);
}
ans[i]=((1+mod-now.val())*inv2+inv2)%mod;
}
ll pw2=ksm(2,size[1]);
for(int i=n;i>=1;i--) ans[i]=(ans[i]-ans[i-1]+mod)*pw2%mod;
ans[n]=(ans[n]-1+mod)%mod;
for(int i=L;i<=R;i++) cout<<ans[i]<<" ";
return 0;
}