【题解】洛谷2081 [NOI2012]迷失游乐园

题解】洛谷2081 [NOI2012]迷失游乐园"/>

【题解】洛谷2081 [NOI2012]迷失游乐园

题外话

这道题很久之前听教练讲过，当时觉得太麻烦就没写，后来拾起来的时候就发现自己不会了 QwQ （可能是因为我太菜了吧） ，于是怒肝了两个下午把它弄了出来，中间还出了一次大锅，所以留个博客以作纪念吧

题面

题面异常简单，就是求一颗基环树上的任意一点往某个方向走到头的路径期望长度。这个一看就是要用某种类似 t r e e D P treeDP treeDP 的方法处理的（但是我一开始没看出来），所以我们可以先从简单问题入手

50分——树上dp

我们先考虑没有环的情况，那显然要用树上DP来解决——我们定义两个数组 u p [ i ] up[i] up[i]、 d o w n [ i ] down[i] down[i] 分别代表从 i i i 节点向上和向下走到头的期望距离

那么 d o w n [ i ] down[i] down[i] 应该是相当好转移的，因为它不牵扯拐弯。做一遍 d f s dfs dfs 然后统计每一个儿子的 d o w n down down 即可求出 d o w n [ i ] down[i] down[i] 了，转移方程用手推一下应该就能出来：
d o w n [ i ] = ∑ i − > j ( d o w n [ j ] + l e n ( i , j ) ) s o n [ i ] down[i]=\frac{\sum_{i->j}(down[j]+len(i,j))}{son[i]} down[i]=son[i]∑i−>j​(down[j]+len(i,j))​
这里 j j j 是 i i i 的每一个儿子， l e n ( i , j ) len(i,j) len(i,j) 表示 i i i 到 j j j 这条边的长度， s o n [ i ] son[i] son[i] 表示 i i i 的儿子数量

但是 u p [ i ] up[i] up[i] 就有点难搞，因为这条路有可能往上走了几步又拐到向下，而且你还得处理每一个位置拐弯的情况。这就非常麻烦了

我们考虑，如果我们处理出了每一个点的 d o w n down down，然后从上往下 d p dp dp，那么我们这条路的期望会是什么样子的呢？

我们从这幅图上可以很清楚的看到：这个期望一共涉及两种方向，也就是上面的 2 2 2 和 $3 $。

这个 2 2 2 就相当于是从 i i i 的父亲 f 出发向下不经过 i i i 的所有路径的期望，可以表示为 d o w n [ f ] × s o n [ f ] − d o w n [ i ] − l e n ( f , i ) down[f]\times son[f]-down[i]-len(f,i) down[f]×son[f]−down[i]−len(f,i)

那如果继续向上，就相当于是从 f f f 向上随便走，其实就是 u p [ f ] up[f] up[f]了。

所以我们就可以总结出一个计算 u p [ i ] up[i] up[i] 的公式了：
u p [ i ] = l e n ( f , i ) + d o w n [ f ] × s o n [ f ] − d o w n [ i ] − l e n ( f , i ) + u p [ f ] d e g [ f ] − 1 up[i]=len(f,i)+\frac{down[f]\times son[f]-down[i]-len(f,i)+up[f]}{deg[f]-1} up[i]=len(f,i)+deg[f]−1down[f]×son[f]−down[i]−len(f,i)+up[f]​
这里 d e g [ f ] deg[f] deg[f] 表示 f f f 的度数，也就是这个点连出的边数。容易看出， d e g [ f ] − 1 = ( s o n [ f ] + 1 ) − 1 = s o n [ f ] deg[f]-1=(son[f] +1)-1=son[f] deg[f]−1=(son[f]+1)−1=son[f]。所以直接把分母改写成 s o n [ f ] son[f] son[f] 即可。

最后怎么统计答案呢？参考一下上面那幅图就可以推出：
a n s = ∑ u p [ i ] + d o w n [ i ] ∗ s o n [ i ] s o n [ i ] + 1 ans=\sum \frac{up[i]+down[i]*son[i]}{son[i]+1} ans=∑son[i]+1up[i]+down[i]∗son[i]​
那么树上的问题就解决了

（对了我这里少说了一句，其实这样写在洛谷上是可以混过两个基环点的哈哈哈哈）

100分——基环树特殊处理

既然环上的点不多，只有20个，我们就可以轻松 d f s dfs dfs 找出这些点并把它们用一个类似链表的方式保存起来（就是保存每一个点的下一位和上一位）

然后我们会发现，这个环貌似对环外的 u p up up 和 d o w n down down 没有任何影响，所以我们就可以对于每一棵小树 d f s dfs dfs 求出 d o w n down down

那么根据刚才的经验，我们就可以通过这个 d o w n down down 来推算每个点的 u p up up了

我们先来说环上的 u p up up 值怎么求：

我们举个例子，如果环上的点是 1 , 2 , 3 , 4 , 5 1,2,3,4,5 1,2,3,4,5，我们钦定方向为顺时针，那么对于 1 1 1 来说走到 2 2 2 的可能性就是 1 1 1。从 2 2 2 走到 3 3 3 的可能性就是 1 s o n [ 2 ] + 1 \frac{1}{son[2]+1} son[2]+11​，从 3 3 3 走到 4 4 4 的可能性就是 1 s o n [ 3 ] + 1 \frac{1}{son[3]+1} son[3]+11​ 。。。以此类推

那么我们就可以顺时针逆时针都跑一遍，然后统计答案时除以 2 即可。

表达式不太好看，所以这里就给出一个顺时针的：
u p [ i ] = ∑ j ! = i j = n e x [ i ] ( ∏ k ! = j k = n e x [ i ] 1 s o n [ k ] + 1 × l e n ( l a s t [ j ] , j ) + d o w n [ j ] ∗ s o n [ j ] s o n [ j ] + 1 ) up[i]=\sum_{j!=i}^{j=nex[i]} (\prod_{k!=j}^{k=nex[i]} \frac{1}{son[k]+1}\times\frac{len(last[j],j)+down[j]*son[j]}{son[j]+1}) up[i]=j!=i∑j=nex[i]​(k!=j∏k=nex[i]​son[k]+11​×son[j]+1len(last[j],j)+down[j]∗son[j]​)
逆时针同理即可。

如果觉得没看懂表达式的话，这里上一段代码和一张图帮助各位理解：

double now=1;
for(int j=nx[x];j!=x;j=nx[j])
{if(/**/) //这里其实还有一个特判，请自行推算up[x]+=now*(h[j]+down[j]*son[j]/(son[j]+1));else /**/;now=now/(son[j]+1);
}

这里 n o w now now 就是上面的 ∏ 1 s o n [ k ] + 1 \prod \frac{1}{son[k]+1} ∏son[k]+11​，而 h [ i ] h[i] h[i] 就是一个预处理的 l e n ( l a s t [ j ] , j ) len(last[j],j) len(last[j],j)。上面所说的特判其实就是从环首走了一圈又回来的状况，请各位自行推算，这里就不再赘述了

还有一个小问题就是如何处理环上各点的儿子的 u p up up 。因为这些点的父节点左右有两条连边，所以这些店需要单独拿出来计算 u p [ i ] up[i] up[i] ：
u p [ i ] = l e n ( f , i ) + d o w n [ f ] × s o n [ f ] − d o w n [ i ] − l e n ( f , i ) + u p [ f ] × 2 d e g [ f ] − 1 up[i]=len(f,i)+\frac{down[f]\times son[f]-down[i]-len(f,i)+up[f]\times2}{deg[f]-1} up[i]=len(f,i)+deg[f]−1down[f]×son[f]−down[i]−len(f,i)+up[f]×2​
注意一下这里的 d e g [ f ] − 1 ≠ s o n [ f ] deg[f]-1\ne son[f] deg[f]−1̸​=son[f]

统计答案的时候与之前的式子相似，树上的按照树上的统计，环上的就是上面加一个 u p [ i ] up[i] up[i] ，下面加 1 1 1 就行了，也就是下面的这个式子：
a n s = ∑ u p [ i ] × 2 + d o w n [ i ] ∗ s o n [ i ] s o n [ i ] + 2 ans=\sum \frac{up[i]\times 2+down[i]*son[i]}{son[i]+2} ans=∑son[i]+2up[i]×2+down[i]∗son[i]​

还有就是这几个期望计算的时候分母都不能是 0 0 0 ，所以需要手动加几个特判才行。

好了多的不说了,具体细节请看代码吧：

code

#include<vector>
#include<string.h>
#include<iostream>
#define N 100005
using namespace std;
int n,m,flag,nexflag,vis[N],son[N],fa[N],nx[N],h[N],nh[N],tag[N];
double ans,down[N],up[N];
struct nod{int to,val;
};
vector<nod> edge[N];
vector<int> lay[N],loop;
void addedge(int u,int v,int w)
{edge[u].push_back((nod){v,w});edge[v].push_back((nod){u,w});
}
void dfs1(int x)
{down[x]=0;for(int i=0;i<edge[x].size();i++){nod nex=edge[x][i];if(!vis[nex.to]){vis[nex.to]=1;fa[nex.to]=x;h[nex.to]=nex.val;dfs1(nex.to);down[x]+=down[nex.to]+nex.val;son[x]++;}}if(son[x]>0)down[x]/=son[x];
}
void dfs2(int x)
{int f=fa[x];if(son[f]>1){if(!tag[x])up[x]=(double)(down[f]*son[f]-down[x]-h[x]+up[f])/(edge[f].size()-1)+h[x];else	up[x]=(double)(down[f]*son[f]-down[x]-h[x]+up[f]*2)/(edge[f].size()-1)+h[x];}else	up[x]=up[f]+h[x];for(int i=0;i<edge[x].size();i++){nod nex=edge[x][i];if(!vis[nex.to]){vis[nex.to]=1;dfs2(nex.to);}}
}
void dfs3(int x,int pre)
{vis[x]=1;if(flag!=0)return;for(int i=0;i<edge[x].size();i++){nod nex=edge[x][i];if(nex.to!=pre){if(vis[nex.to]){if(flag!=0)	return;flag=x;nexflag=nex.to;fa[nex.to]=x;nx[x]=nex.to;h[nex.to]=nh[x]=nex.val;return;}if(flag!=0)	return;fa[nex.to]=x;nx[x]=nex.to;h[nex.to]=nh[x]=nex.val;dfs3(nex.to,x);if(flag!=0)	return;}}
}
void cl_vis()
{memset(vis,0,sizeof(vis));for(int i=0;i<loop.size();i++)vis[loop[i]]=1;
}
int main()
{int u,v,w;cin>>n>>m;for(int i=1;i<=m;i++){cin>>u>>v>>w;addedge(u,v,w);}if(m==n-1){vis[1]=1;dfs1(1);memset(vis,0,sizeof(vis));vis[1]=1;dfs2(1);for(int i=1;i<=n;i++)ans+=(double)(down[i]*son[i]+up[i])/(son[i]+(fa[i]!=0?1:0));printf("%.5f",ans/n);}else{dfs3(1,0);for(int i=flag;i!=nexflag;i=fa[i])loop.push_back(i),vis[i]=1;loop.push_back(nexflag);vis[nexflag]=1;cl_vis();int sz=loop.size();for(int i=0;i<sz;i++)dfs1(loop[i]);for(int i=sz-1;i>=0;i--){int x=loop[i];double now=1;up[x]=0;for(int j=nx[x];j!=x;j=nx[j]){if(nx[j]!=x)up[x]+=now*(h[j]+down[j]*son[j]/(son[j]+1));else	up[x]+=now*(h[j]+down[j]);now=now/(son[j]+1);}now=1;for(int j=fa[x];j!=x;j=fa[j]){if(fa[j]!=x)up[x]+=now*(nh[j]+down[j]*son[j]/(son[j]+1));else	up[x]+=now*(nh[j]+down[j]);now=now/(son[j]+1);}up[x]/=2;}cl_vis();for(int i=0;i<sz;i++)for(int j=0;j<edge[loop[i]].size();j++){nod nex=edge[loop[i]][j];if(!vis[nex.to])vis[nex.to]=tag[nex.to]=1,dfs2(nex.to);}	cl_vis();for(int i=1;i<=n;i++){if(!vis[i])ans+=(double)(down[i]*son[i]+up[i])/(son[i]+1);else	ans+=(double)(down[i]*son[i]+up[i]*2)/(son[i]+2);}printf("%.5f",ans/n);}return 0;
}