题解：CF2028E Alice's Adventures in the Rabbit Hole

挺有意思的一道题。

设

d(u)

表示在

u

的儿子当中最靠近叶节点的儿子。显然这个东西可以直接搜索出来。

以下设

v = d(u)

。

设

f_u

表示 Alice 从

u

爬到根的概率。
分两种情况：

这次由她走。因为她想跑掉，所以她会选择更靠近根节点的点走，那她肯定是选父节点，则概率为 $f_{fa}$ 。
这次由女王走。因为女王想杀死她，所以肯定会将她拉到一个最靠近叶节点的位置，同时只能移动一步，所以这个点一定是 $v$ ，则概率为 $f_v$ 。

所以可以得出：

f_u = \frac{1}{2} (f_v + f_{fa})

乘以

\frac{1}{2}

是因为两种情况要平摊

1

的概率。

显然，这个东西有后效性无法转移，所以要让它变一下形式。

由此引发猜想：

f_u

可以表示成

k_uf_{fa}

的形式，那我们尝试解一下。

有：

f_u = \frac{1}{2} (f_v+f_{fa})

2f_u = f_v+f_{fa}

2f_u = k_vf_u+f_{fa}

(2-k_v)f_u=f_{fa}

f_u = \frac{1}{2 - k_v}f_{fa}

\therefore

k_u = \frac{1}{2 - k_v}

。

所以我们就只需要将

k_u

递归求出，再递归求出

f_u

就好了。

关于取模的话，用逆元求出就好了。

代码

CPP

#include<iostream>
#include<cstring>
using namespace std;
int n;
const int N=5e5+10,mod=998244353;
int h[N],e[N],ne[N],idx,g[N],dep[N];
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
long long f[N],k[N];
int la;
void init(){
	for(int i=1;i<=la;i++){
		h[i]=-1,f[i]=k[i]=g[i]=dep[i]=0;
	}
	idx=0;
}
long long pow(long long a,int b){
	long long res=1;
	while(b){
		if(b&1){
			res=res*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
long long ny(long long a,long long b){
	return a*pow(b,mod-2)%mod;
}
void dfs1(int u,int fa){
	dep[u]=2e9;
	int cnt=0;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa){
			continue;
		}
		cnt++;
		dfs1(j,u);
		dep[u]=min(dep[u],dep[j]+1);
		if(dep[j]+1==dep[u]){
			g[u]=j;
		}
	}
	if(!cnt){
		dep[u]=0;
	}
}
void dfs2(int u,int fa){
	int cnt=0;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa){
			continue;
		}
		cnt++;
		dfs2(j,u);
	}
	if(cnt){
		int v=g[u];
		k[u]=ny(1ll,(2-k[v]+mod)%mod);
	}
}
void dfs3(int u,int fa){
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(j==fa){
			continue;
		}
		f[j]=k[j]*f[u]%mod;
		dfs3(j,u);
	}
}
int main(){
	int t;
	cin>>t;
	la=N-1;
	while(t--){
		init();
		scanf("%d",&n);
		for(int i=1;i<n;i++){
			int a,b;
			scanf("%d%d",&a,&b);
			add(a,b),add(b,a);
		}
		dfs1(1,-1);
		dfs2(1,-1);
		f[1]=1ll;
		dfs3(1,-1);
		for(int i=1;i<=n;i++){
			printf("%lld ",f[i]);
		}
		printf("\n");
		la=n;
	}
	return 0;
}

题解：CF2028E Alice's Adventures in the Rabbit Hole

文章操作

代码

相关推荐

评论

题解：CF2028E Alice's Adventures in the Rabbit Hole