[ZJOI2019]Minimax搜索

先求出根节点的权值\(w\)。根据套路，我们对于每个\(k\)，计算\(w(s)\leq k\)的方案数，差分得到答案。为了方便，接下来考虑计算概率而不是方案数。

可以发现，对于一个给定的有解的子集，在最优解下，根节点的权值一定可以是\(w+1\)或\(w-1\)。如果我们希望把根节点的权值变为\(w+1\)，那么我们一定只会改变点权\(\leq w\)的点，\(w-1\)同理。

我们特殊考虑点权为\(w\)的点。如果控制集合包含这个点，那么答案一定为\(1\)（因为所有点的点权两两不同），所以\(ans_1=\frac{1}{2}\)。接下来，我们可以钦定控制集合不包含这个点。

这时，如果我们希望把根节点的权值变为\(w+1\)，我们一定只会改变点权\(<w\)的点，\(w-1\)同理。这样这两类点就无交了。所以我们可以算出通过改变点权\(<w\)的点不能使根节点的权值变为\(w+1\)的概率\(f\)，和通过改变点权\(>w\)的点不能使根节点的权值变为\(w-1\)的概率\(g\)，乘起来就是答案。

转移显然，分奇偶层讨论一下就行了。为了方便，我们将偶数层的\(f,g\)值取反，这样对于每一层转移都是一样的，就可以直接上动态DP了。

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

const int mod=998244353;

const int inv2=(mod+1)>>1;

int gi() {

	int x=0,o=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if(ch=='-') o=-1,ch=getchar();

	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();

	return x*o;

}

int qpow(int a,int b) {

	int ret=1;

	while(b) {

		if(b&1) ret=1ll*ret*a%mod;

		a=1ll*a*a%mod,b>>=1;

	}

	return ret;

}

struct num {

	int x,y;

	num(int x=1,int y=0):x(x),y(y) {}

	void mul(const num &A) {

		x=1ll*x*A.x%mod,y+=A.y;

	}

	void div(const num &A) {

		x=1ll*x*qpow(A.x,mod-2)%mod,y-=A.y;

	}

	int val() {

		return y?0:x;

	}

} g[N][2];

int add(int a,int b) {

	return a+b>=mod?a+b-mod:a+b;

}

int sub(int a,int b) {

	return a-b<0?a-b+mod:a-b;

}

num trs(int x) {

	return x?num(x,0):num(1,1);

}

vector<int> E[N];

int n,L,R,pw=1,fa[N],dep[N],siz[N],son[N],f[N][2],top[N],tim=0,dfn[N],bot[N],id[N],w,t,rt[N],tot=0,ls[N*50],rs[N*50],s[N*50][2],p[N*50][2],ans[N];

bool lf[N];

int dfs1(int u) {

	siz[u]=1;

	if(fa[u]&&E[u].size()==1) { lf[u]=1;pw=(pw<<1)%mod;return u; }

	int w=dep[u]?n:0;

	for(auto v:E[u]) if(v!=fa[u]) fa[v]=u,dep[v]=dep[u]^1,t=dfs1(v),siz[u]+=siz[v],siz[son[u]]<siz[v]?son[u]=v:0,w=dep[u]?min(w,t):max(w,t);

	return w;

}

void dfs2(int u) {

	bot[top[u]]=u;id[dfn[u]=++tim]=u;f[u][0]=f[u][1]=1;

	if(son[u]) {

		top[son[u]]=top[u],dfs2(son[u]);

		for(int i=0;i<2;i++) f[u][i]=1ll*f[u][i]*sub(1,f[son[u]][i])%mod;

	}

	else f[u][0]=(t=((u<=w)^dep[u])),g[u][0].mul(trs(t)),f[u][1]=(t=((u<w)^dep[u])),g[u][1].mul(trs(t));

	for(auto v:E[u])

		if(v!=fa[u]&&v!=son[u]) {

			top[v]=v,dfs2(v);

			for(int i=0;i<2;i++) g[u][i].mul(trs(t=sub(1,f[v][i]))),f[u][i]=1ll*f[u][i]*t%mod;

		}

}

#define chk if(l==r) { for(int i=0;i<2;i++) s[x][i]=p[x][i]=g[id[l]][i].val(); return; }

#define up for(int i=0;i<2;i++) s[x][i]=add(s[ls[x]][i],1ll*(((mid-l+1)&1)?mod-p[ls[x]][i]:p[ls[x]][i])*s[rs[x]][i]%mod),p[x][i]=1ll*p[ls[x]][i]*p[rs[x]][i]%mod;

void build(int &x,int l,int r) {

	x=++tot;chk;

	int mid=(l+r)>>1;

	build(ls[x],l,mid),build(rs[x],mid+1,r);

	up;

}

void mdf(int x,int l,int r,int k) {

	chk;

	int mid=(l+r)>>1;

	k<=mid?mdf(ls[x],l,mid,k):mdf(rs[x],mid+1,r,k);

	up;

}

void mdf(int u,int x) {

	int v=top[u],w=fa[v];

	if(w) g[w][x].div(trs(sub(1,s[rt[v]][x])));

	mdf(rt[v],dfn[v],dfn[bot[v]],dfn[u]);

	if(w) g[w][x].mul(trs(sub(1,s[rt[v]][x]))),mdf(w,x);

}

int main() {

	n=gi(),L=gi(),R=gi();

	for(int i=1,u,v;i<n;i++) u=gi(),v=gi(),E[u].push_back(v),E[v].push_back(u);

	w=dfs1(1);top[1]=1;dfs2(1);

	for(int i=1;i<=n;i++) if(top[i]==i) build(rt[i],dfn[i],dfn[bot[i]]);

	ans[1]=pw=1ll*pw*inv2%mod;

	for(int i=2;i<n;i++) {

		if((t=w+1-i)>0&&lf[t]) g[t][0]=trs(inv2),mdf(t,0);

		if((t=w+i-1)<=n&&lf[t]) g[t][1]=trs(inv2),mdf(t,1);

		ans[i]=1ll*add(1ll*sub(s[1][1],1)*s[1][0]%mod,2)*pw%mod;

	}

	ans[n]=(pw+pw-1)%mod;

	for(int i=L;i<=R;i++) printf("%d ",sub(ans[i],ans[i-1]));

	return 0;

}

巴特西

[ZJOI2019]Minimax搜索

最新文章

热门文章