设 \(F_{i}\) 为经过点 \(i\) 时的期望 , \(in_{i}\) 为点 \(i\) 度数 , 我们易得 :
\(\begin{aligned} F_{t} &= 1\\ F_{s} &= 1+ \frac{F_{fa}}{in_{fa}} + \sum_{v \in V_{i}}\frac{F_{v}}{in_{v}} \\ F_{u} &= \frac{F_{fa}}{in_{fa}} + \sum_{v \in V_{i}}\frac{F_{v}}{in_{v}}\;\;\;(u!=T||S) \end{aligned}\)
我们发现 \(F_{i}\) 只和它的父亲和有直接相连的儿子有关 , 可以写成一个方程组 , 用高斯消元解决 , 时间复杂度是 \(\mathcal{O}(N^3)\)
不足以通过本题 , 但是本题有一个优秀的性质 , 即是这是在一棵树上,当我们来到叶子节点时 , 便可以求解其系数 , 接下来就可以从下向上的解出每一项系数
按照我们刚才所说的列出树上高斯消元套路式子 \((powered\; by\) @ckain$ )$ :
设 \(F_{i}=g_{i}F_{fa} + c_{i}\)
将 \(2,3\) 写成一个式子:
\(\begin{aligned} \displaystyle F_{u} &= \frac{F_{fa}}{in_{fa}} + \sum_{v \in V_{i}}\frac{F_{v}}{in_{v}} + [u = S] \;\;\; (u!=T)\\ \displaystyle &= \frac{F_{fa}}{in_{fa}}+ \sum_{v \in V_{i}}\frac{g_{v}F_{u}+c_{v}}{in_{v}}+[u=S]\\ \displaystyle &=\frac{F_{fa}}{in_{fa}}+ \sum_{v \in V_{i}}\frac{g_{v}}{in_{v}}F_{u}+\sum_{v \in V_{i}}\frac{c_{v}}{in_{v}}+[u=S]\\ \end{aligned}\)
移项得:
\[(1-\sum_{v \in V_{i}}\frac{g_{v}}{in_{v}})F_{u}=\frac{F_{fa}}{in_{fa}}+\sum_{v \in V_{i}}\frac{c_{v}}{in_{v}}+[u=S]\;\;\; (u!=T) \]此时我们就可以得知 \(g_{i} \& c_{i}\) 的式子了 \((\) 把左边除过去
时间复杂度 \(\mathcal{O}(N)\)
贴个代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd(void){
int s=0, f=1; char c=getchar();
while(c<'0' || c>'9') {if(c=='-') f=0; c=getchar();}
while(c>='0' && c<='9') {s=s*10+c-'0'; c=getchar();}
return f? s:-s;
}
const int N=2e5+10,mod=998244353;
int n;
int S,T;
int f[N],g[N],c[N],in[N];
vector<int> edge[N];
inline int qpow(int b,int p){
int res=1;
while(p){
if(p&1)res=res*b%mod;
b=b*b%mod;
p>>=1;
}
return res;
}
void dfs1(int x,int fa){
int gv=0,cv=0;
for(int i:edge[x]){
if(i==fa)continue;
dfs1(i,x);
gv+=g[i]*qpow(in[i],mod-2)%mod;gv%=mod;
cv+=c[i]*qpow(in[i],mod-2)%mod;cv%=mod;
}
gv=(1-gv+mod)%mod;
gv=qpow(gv,mod-2);
cv+=(x==S);
if(fa!=T)g[x]=qpow(in[fa],mod-2)*gv%mod;
c[x]=cv*gv%mod;
}
void dfs2(int x,int fa){
if(x!=T)f[x]=(g[x]*f[fa]%mod+c[x])%mod;
for(int i:edge[x]){
if(i==fa)continue;
dfs2(i,x);
}
}
signed main(){
n=rd();S=rd();T=rd();
for(int i=1;i<n;i++){
int x=rd(),y=rd();
in[x]++;in[y]++;
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs1(T,0);
f[T]=1;
dfs2(T,0);
for(int i=1;i<=n;i++)printf("%lld ",f[i]);
return 0;
}