题解：CF2028E Alice's Adventures in the Rabbit Hole
ny_jerry2
·
·
题解
挺有意思的一道题。
设 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}
所以我们就只需要将 $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;
}
```