\(\texttt{「HDU4035」 Maze}\)
\(\texttt{Describe}\)
迷宫有 \(n\) 个房间，由 \(n-1\) 条隧道连通起来形成了一棵树，从结点 \(1\) 出发，在每个结点 \(i\) 都有 \(3\) 种可能，每种可能概率都互斥：
- \(K_i\) 的概率被杀死，回到结点1处；
- \(E_i\) 的概率找到出口，走出迷宫；
- 等概率走一条和该点相连的边；
求走出迷宫的需要走的边数的期望值。
\(\texttt{Input Format}\)
第一行输入正整数 \(T\)，表示测试数据组数。
对于每一组数据第一行为正整数 \(n\) 表示节点数目，接下来 \(n-1\) 行每行给出两个整数 \(u,v\) 表示树上一条无向边 \((u,v)\)。最后 \(n\) 行中的第 \(i\) 行给出两个整数 \(k_i,e_i\) 表示 \(100K_i=k_i,100E_i=e_i\)。
\(\texttt{Output Format}\)
对于第 \(t(1\le t\le T)\) 组测试数据，如果存在答案为 \(E\) 输出 Case t: E；如果无法走出迷宫，那么输出 Case t: impossible。
\(\texttt{Example In 1}\)
3
3
1 2
1 3
0 0
100 0
0 100
3
1 2
2 3
0 0
100 0
0 100
6
1 2
2 3
1 4
4 5
4 6
0 0
20 30
40 30
50 50
70 10
20 60
\(\texttt{Example Out 1}\)
Case 1: 2.000000
Case 2: impossible
Case 3: 2.895522
\(\texttt{Data}\)
\(1\le T\le 30,2\le n\le 10000\)
\(0\le k_i,e_i\le 100,k_i+e_i\le 100,k_1=e_1=0\)
保证给出数据是一棵树。
\(\texttt{Solution}\)
考虑期望 \(\text{DP}\)，后文中 \(d(u)\) 表示点 \(u\) 的邻接点数目。考虑 \(f(u)\) 为从点 \(u\) 出发走出迷宫的期望边数，易得：
\[f(u)=K_uf(1)+E_u\times 0+\dfrac{1-K_u-E_u}{d(u)}\sum_{(u,v)}(f(v)+1) \]这个方程显然具有后效性，于是考虑高斯消元 \(\mathcal O(n^3)\) 求解，发现 \(n\le 10000\)，过不了。发现状态方程由 \(f(1)\) 和 \(f(\text{fa}_u)\) 和子节点构成，用经典处理方式断言 \(f(u)=a(u)f(1)+b(u)f(\text{fa}_u)+c(u)\)。尝试用数学归纳法证明。
对于叶节点，显然有
此时 \(a(u)=K_u,b(u)=1-K_u-E_u,c(u)=1-K_u-E_u\)
对于节点 \(u\) 假设其子节点都满足我们所断言的，验证节点 \(u\)：
整理原式后有
\[(1-\dfrac{1-K_u-E_u}{d(u)}\sum_{v\in\text{son}(u)}b(v)))f(u)=(K_u+\dfrac{1-K_u-E_u}{d(u)}\sum_{v\in\text{son}(u)}a(v))f(1)+\dfrac{1-K_u-E_u}{d(u)}f(\text{fa}_u)+(\dfrac{1-K_u-E_u}{d(u)}+1-K_u-E_u+\dfrac{1-K_u-E_u}{d(u)}\sum_{v\in\text{son}(u)}c(v)) \]发现满足我们所断言的，设 \(V=(1-\dfrac{1-K_u-E_u}{d(u)}\sum_{v\in\text{son}(u)}b(v)))\)，同时推出
\[\begin{aligned} &a(u)=\dfrac{K_u+\dfrac{1-K_u-E_u}{d(u)}\sum_{v\in\text{son}(u)}a(v)}{V}\\\\ &b(u)=\dfrac{\dfrac{1-K_u-E_u}{d(u)}}{V}\\\\ &c(u)=\dfrac{\dfrac{1-K_u-E_u}{d(u)}+1-K_u-E_u+\dfrac{1-K_u-E_u}{d(u)}\sum_{v\in\text{son}(u)}c(v)}{V} \end{aligned} \]自底向上进行递推即可 \(\mathcal O(n)\) 解决。
\(\texttt{Code}\)
点击查看代码
#include<cstdio>
#include<cmath>
#include<cstring>
#define ll long long
#define MAXN (10005)
#define eps (1e-8)
using namespace std;
void read(ll &x)
{
char ch=0;bool f=0;x=0;
while(ch<'0'||ch>'9'){f|=!(ch^'-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x=f?-x:x;
}
void write(ll x,bool bk)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(!x)
{
if(!bk) putchar('0');
return;
}
write(x/10,1);
putchar((x%10)^48);
}
void print(ll x,char ch)
{
write(x,0);
if(ch) putchar(ch);
}
ll cnt;
ll head[MAXN],nxt[MAXN<<1],to[MAXN<<1];
void add(ll u,ll v)
{
++cnt;
to[cnt]=v;
nxt[cnt]=head[u],head[u]=cnt;
}
ll t,n;
ll d[MAXN];
double ans;
double K[MAXN],E[MAXN],a[MAXN],b[MAXN],c[MAXN];
bool check(ll u,ll fa)
{
if(fabs(K[u]-1.0)<eps) return 0;
else if(E[u]>eps) return 1;
for(ll i=head[u];i;i=nxt[i])
{
ll v=to[i];
if((v^fa)&&check(v,u)) return 1;
}
return 0;
}
void dfs(ll u,ll fa)
{
a[u]=0,b[u]=0,c[u]=0;
ll tmp=0;
double suma=0,sumb=0,sumc=0;
for(ll i=head[u];i;i=nxt[i])
{
ll v=to[i];
if(v^fa)
{
++tmp;
dfs(v,u);
suma+=a[v];
sumb+=b[v];
sumc+=c[v];
}
}
if(!tmp)
{
a[u]=K[u];
b[u]=1-K[u]-E[u];
c[u]=1-K[u]-E[u];
// printf("a(%lld)=%lf,b(%lld)=%lf,c(%lld)=%lf\n",u,a[u],u,b[u],u,c[u]);
return;
}
suma*=(1.0-K[u]-E[u]);
sumb*=(1.0-K[u]-E[u]);
sumc*=(1.0-K[u]-E[u]);
if(!(u^1))
{
ans=(1.0+sumc/d[1])/(1.0-K[1]-(suma+sumb)/d[1]);
return;
}
double Div=1-sumb/d[u];
a[u]=(K[u]+suma/d[u])/Div;
b[u]=(1-K[u]-E[u])/d[u]/Div;
c[u]=(sumc/d[u]+1.0-K[u]-E[u])/Div;
// printf("a(%lld)=%lf,b(%lld)=%lf,c(%lld)=%lf\n",u,a[u],u,b[u],u,c[u]);
}
int main()
{
read(t);
for(ll JIEGE=1;JIEGE<=t;JIEGE++)
{
memset(d,0,sizeof(d));
memset(head,0,sizeof(head));
cnt=0;
read(n);
for(ll i=1;i<n;i++)
{
ll x,y;
read(x),read(y);
add(x,y);
add(y,x);
++d[x],++d[y];
}
for(ll i=1;i<=n;i++)
{
scanf("%lf%lf",&K[i],&E[i]);
K[i]/=100.0,E[i]/=100.0;
}
if(!check(1,0))
{
printf("Case %lld: impossible\n",JIEGE);
continue;
}
dfs(1,0);
printf("Case %lld: %.10lf\n",JIEGE,ans);
}
}