posted on 2022-08-17 12:33:51 | under 题解 | source
problem
https://vjudge.net/problem/HDU-4035
SHY 在一棵树上随机游走，从根节点出发，每次有 \(k_u\) 的几率回到根节点，\(e_u\) 的几率到达出口，否则随机选择一个与它相连的节点并走过去，求期望多少步能走到出口。\(1\leq n\leq 10^4\)。
solution
令根为 \(1\)，\(t_u=1-k_u-e_u\)，记 \(f_u\) 表示从点 \(u\) 出发走到出口的期望步数，\(p\) 为 \(u\) 的父亲，\(v\) 为 \(u\) 的儿子，\(d\) 为点 \(u\) 的度数。显然有：
\[\begin{aligned} f_u&=k_u\times f_1+t_u\times\sum_{v\in son(u)}d^{-1}(f_v+1)+t_u\times d^{-1}(f_p+1)\\ &=k_u\times f_1+t_u\times d^{-1}\times\left(f_p+1+\sum_{v\in son(u)}(f_v+1)\right)\\ &=k_u\times f_1+t_u\times d^{-1}\times f_p+t_u\times d^{-1}\times \sum_{v\in son(u)}f_v+t_u\\ \end{aligned}\]我们发现这个式子有后效性，那么当然不能打高斯消元，考虑令 \(f_u=a_u\times f_1+b_u\times f_p+c_u\)。分类讨论：对于一片叶子，显然有 \(a_u=k_u,b_u=c_u=t_u\)。
对于非叶子节点 \(u\)，我们考虑拆掉 \(\sum_{v\in son(u)}f_v=f_1\times\sum a_v+f_u\times\sum b_v+\sum c_v\)。
\[\begin{aligned} f_u&=k_u\times f_1+\frac{t_u}{d}\times f_p+\frac{t_u}{d}\times \sum_{v\in son(u)}f_v+t_u\\ &=k_u\times f_1+\frac{t_u}{d}\times f_p+\frac{t_u}{d}\times \left(f_1\times\sum a_v+f_u\times\sum b_v+\sum c_v\right)+t_u\\ &=\left(k_u+\frac{t_u}{d}\times\sum a_v\right)\times f_1+\frac{t_u}{d}\times f_p+\left(\frac{t_u}{d}\times\sum b_v\right)\times f_u+\left(t_u+\frac{t_u}{d}\times\sum c_v\right) \end{aligned}\]接下来是点睛之笔：把 \(f_u\) 项移到等式左边！
\[\begin{aligned} f_u&=\left(k_u+\frac{t_u}{d}\times\sum a_v\right)\times f_1+\frac{t_u}{d}\times f_p+\left(\frac{t_u}{d}\times\sum b_v\right)\times f_u+\left(t_u+\frac{t_u}{d}\times\sum c_v\right)\\ f_u-\left(\frac{t_u}{d}\times\sum b_v\right)\times f_u&=\left(k_u+\frac{t_u}{d}\times\sum a_v\right)\times f_1+\frac{t_u}{d}\times f_p+\left(t_u+\frac{t_u}{d}\times\sum c_v\right)\\ \left(1-\frac{t_u}{d}\times\sum b_v\right)\times f_u&=\left(k_u+\frac{t_u}{d}\times\sum a_v\right)\times f_1+\frac{t_u}{d}\times f_p+\left(t_u+\frac{t_u}{d}\times\sum c_v\right)\\ \end{aligned}\]将 \(1-\frac{t_u}{d}\times\sum b_v\) 作为分母移过去，我们终于得到：
\[\begin{aligned} a_u&=\frac{k_u+\frac{t_u}{d}\times\sum a_v}{1-\frac{t_u}{d}\times\sum b_v}\\ b_u&=\frac{t_u\times d^{-1}}{1-\frac{t_u}{d}\times\sum b_v}\\ c_u&=\frac{t_u+\frac{t_u}{d}\times\sum c_v}{1-\frac{t_u}{d}\times\sum b_v}\\ \end{aligned}\]这里的每一项都只和 \(u,v\) 有关，可以做树型 DP 了！自底向上更新 \(a_u,b_u,c_u\) 即可。我们其实并不需要计算 \(f_u\)。
最终的答案是 \(f_1=a_1\times f_1+c_1\)，可化简为 \(f_1=\frac{c_1}{1-a_1}\)。
什么时候会无解呢？分母是 \(0\) 的时候。
- \(d=0\) 根本除不动（？？？？？）
- 计算过程中 \(1-\frac{t_u}{d}\times\sum b_v=0\)，寄。
- 最终 \(a_1=1\)，相减又得 \(0\)，寄。
那么我们可以写代码了。
code
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const double eps=1e-9;
template<int N,int M,class T=int> struct graph{
int head[N+10],nxt[M*2+10],cnt;
struct edge{
int u,v;T w;
edge(int u=0,int v=0,T w=0):u(u),v(v),w(w){}
} e[M*2+10];
graph(){memset(head,cnt=0,sizeof head);}
edge operator[](int i){return e[i];}
void add(int u,int v,T w=0){e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
void link(int u,int v,T w=0){add(u,v,w),add(v,u,w);}
};
int n,deg[10010];
double a[10010],b[10010],c[10010],k[10010],t[10010];
graph<10010,10010> g;
int dfs(int u,int fa){
if(deg[u]==1&&fa) return a[u]=k[u],b[u]=c[u]=t[u],1;
// ^~~~ important!
double sa=0,sb=0,sc=0;
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v; if(v==fa) continue;
if(!dfs(v,u)) return 0;
sa+=a[v],sb+=b[v],sc+=c[v];
}
double del=t[u]/deg[u],tmp=1-del*sb;
if(fabs(tmp)<eps) return 0;
a[u]=(k[u]+del*sa)/tmp;
b[u]=del/tmp;
c[u]=(t[u]+del*sc)/tmp;
return 1;
}
int mian(){
for(int i=1,u,v;i<n;i++) scanf("%d%d",&u,&v),g.link(u,v),deg[u]++,deg[v]++;
for(int u=1;u<=n;u++) scanf("%lf%lf",&k[u],&t[u]),k[u]/=1e2,t[u]/=1e2,t[u]=1-t[u]-k[u];
if(dfs(1,0)&&fabs(1-a[1])>eps) printf("%.6lf\n",c[1]/(1-a[1]));
else puts("impossible");
return 0;
}
void reset(){
static int ccf=0;
printf("Case %d: ",++ccf);
memset(a,0,sizeof a);
memset(b,0,sizeof b);
memset(c,0,sizeof c);
memset(k,0,sizeof k);
memset(t,0,sizeof t);
memset(deg,0,sizeof deg);
memset(g.head,g.cnt=0,sizeof g.head);
}
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
for(scanf("%*d");~scanf("%d",&n);reset(),mian());
return 0;
}