P2081 [NOI2012] 迷失游乐园

$\color{deeppink}link$

$n$ 个点、有边权的基环树，随机游走，不经过重复的点，知道不能走。求期望路径长度。

先看树怎么求。

令 $f_{x}$ 表示从 $x$ 开始向下走的期望路径长度，则有

$f_{x}=\frac1{\vert S_x\vert} \sum_{v\in S_x}(f_v+w_{x,v})$

再令 $g_x$ 表示从 $x$ 开始向上的期望长度，$fa$ 代表 $x$ 的父亲，$w$ 为 $x$ 到 $fa$ 的路径长度，则有

$g_x= \left\{ \begin{aligned} &w+\frac{f_{fa}\times\vert S_{fa}\vert+g_{fa}-f_x-w}{\vert S_{fa}\vert} && fa\not=root\\ &w+\frac{f_{fa}\times\vert S_{fa}\vert-f_x-w}{\vert S_{fa}\vert-1} && fa=root\\ &0&&x=root \end{aligned} \right.$

还要特判当 $fa=root$ 且 $\vert S_{fa}\vert=1$ 的情况，此时 $g_{x}=w$。

如此，树上的 50pts 就得到了。

考虑基环树与树的不同。

其实对于每个点，他们的 $f$ 数组的转移方式不会变，对于每个不在环上的点，他们 $g$ 的转移方式也不会变。

但是，若 $fa=root$ 时，$g_x=w+\dfrac{f_{fa}\times\vert S_{fa}\vert-f_x-w+2\times g_{fa}}{\vert S_{fa}+1\vert}$。

由于环上的点只有 20 个，那么在环上的点可以直接搜。这个点开始，不能走向他子树，其他都可以走，然后再 dfs 一遍即可求出他的 $g$。

每个点对答案的贡献是

$\left\{ \begin{aligned} &\frac1n\frac1{\vert S_i+1\vert}\times(f_{i}\times \vert S_i\vert+g_i)&&i\not\in T\\ &\frac1n\frac1{\vert S_i+2\vert}\times(f_{i}\times \vert S_i\vert+2g_i)&&i\in T \end{aligned} \right.$

其中 $T$ 是环上的点的集合，若数据是树，则树的根的贡献是 $f_{root}$。时间是 $O(20n)$。

警钟敲烂：用 topo 排序求环时，顺便把 $f$ 给算了的，没有将环上的 $f$ 除一个 $\vert S\vert$，搞完之后还要单独除。

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=4e5+500;

struct node
{
	int u,v,w,nxt;
}e[N];

int n,m,in[N],son[N],head[N],inque[N],cnt,vis[N],fa[N];
db f[N],g[N],ans;

void topo()
{
	for(int i=1;i<=cnt;i++)++in[e[i].u];
	queue<int>q;
	for(int i=1;i<=n;i++)if(in[i]==1)q.push(i);
	while(!q.empty())
	{
		int x=q.front();q.pop();inque[x]=1;
		if(son[x])f[x]/=son[x];
		for(int i=head[x];i;i=e[i].nxt)
		{
			int v=e[i].v;
			--in[v];
			if(in[v]==1)q.push(v);
			if(!inque[v])
			{
				++son[v];fa[x]=v;
				f[v]+=f[x]+e[i].w;
			}
		}
	}
}

db dfs(int x,int p)
{
	vis[x]=1;int siz=0;db ans=0;
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if((x==p&&fa[v]==x)||vis[v])continue;
		ans+=dfs(v,p)+e[i].w;++siz;
	}
	vis[x]=0;
	if(!siz)return 0;
	return ans/siz;
}

void get_g(int x)
{
	if(in[x]>1)g[x]=dfs(x,x);
	for(int i=head[x];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if(fa[v]!=x)continue;
		if(!fa[x])
		{
			if(n==m)g[v]=e[i].w+(f[x]*son[x]-f[v]-e[i].w+2*g[x])/(son[x]+1);
			else
			{
				if(son[x]==1)g[v]=e[i].w;
				else g[v]=e[i].w+(f[x]*son[x]-f[v]-e[i].w)/(son[x]-1);
			}
		}
		else g[v]=e[i].w+(f[x]*son[x]+g[x]-f[v]-e[i].w)/son[x];
		get_g(v);
	}
}

main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[++cnt]=(node){u,v,w,head[u]};head[u]=cnt;
		e[++cnt]=(node){v,u,w,head[v]};head[v]=cnt;
	}
	topo();
	for(int i=1;i<=n;i++)if(!inque[i]&&son[i])f[i]/=son[i];
	for(int i=1;i<=n;i++)if(!fa[i])get_g(i);
	for(int i=1;i<=n;i++)
	{
		if(!inque[i])ans+=(f[i]*son[i]+2*g[i])/(son[i]+2);
		else if(fa[i])ans+=(f[i]*son[i]+g[i])/(son[i]+1);
		else ans+=f[i];
	}
	cout<<fixed<<setprecision(6)<<ans/n;
}