傳送門

題意：給一棵$n$個點的帶邊權樹或基環樹，隨機選一個點作為起點，每次隨機走到一個相鄰未走過的位置，直到無路可走。求期望路徑長度。

$n\le 10^5$,為基環樹時環的大小不超過$20$

先考慮樹怎么做廢話

先只考慮從根往下走

顯然就是

$$f_u=\frac{{\sum }_{v\in son(u)}w(u,v)+f(v)}{|son(u)|}$$

考慮其他位置

再考慮強制第一步往上走，然后強行不走回來的期望為$g$

方程見代碼

對于基環樹，$f$不受影響。

對于環上的點兩個方向帶著走到這里的概率和距離轉一圈，算出$g$，樹上點方程不變。

然后就可以了

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 100005 #define MAXM 200005 using namespace std; struct edge{int u,v,w;}e[MAXM]; int head[MAXN],nxt[MAXM],cnt; inline int read() {int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } void addnode(int u,int v,int w) {e[++cnt]=(edge){u,v,w};nxt[cnt]=head[u];head[u]=cnt; } int n,m,son[MAXN]; double F[MAXN],G[MAXN]; namespace Tree {void dfs(int u,int f){for (int i=head[u];i;i=nxt[i])if (e[i].v!=f){++son[u];dfs(e[i].v,u);F[u]+=F[e[i].v]+e[i].w;}if (son[u]) F[u]/=son[u];}void DFS(int v,int f){int u=e[f].u;G[v]=e[f].w+((u==1&&son[u]==1)? 0:((G[u]+F[u]*son[u]-F[v]-e[f].w)/(son[u]-(u==1))));for (int i=head[v];i;i=nxt[i])if (e[i].v!=u)DFS(e[i].v,i);}void solve(){dfs(1,0);for (int i=head[1];i;i=nxt[i]) DFS(e[i].v,i);double ans=F[1];for (int i=2;i<=n;i++) ans+=G[i]/(son[i]+1)+F[i]*son[i]/(son[i]+1);printf("%.5f",ans/n);} } namespace Circle {bool vis[MAXN],isrt[MAXN];int rt[MAXN],w[MAXN],tot,tmp;void findroot(int u,int f){vis[u]=true;for (int i=head[u];i;i=nxt[i])if (!vis[e[i].v]&&e[i].v!=rt[1]){findroot(e[i].v,u);if (isrt[e[i].v]&&e[i].v!=tmp) isrt[rt[++tot]=u]=true,w[tot]=e[i].w;}elseif (e[i].v!=f&&e[i].v!=rt[1])isrt[rt[tot=1]=u]=true,w[1]=e[i].w,tmp=e[i].v;vis[u]=false;}void DFS(int v,int f){int u=e[f].u;if (isrt[u]) G[v]=e[f].w+2.0/(son[u]+1)*G[u]+(F[u]*son[u]-F[v]-e[f].w)/(son[u]+1);else G[v]=e[f].w+(G[u]+F[u]*son[u]-F[v]-e[f].w)/son[u];for (int i=head[v];i;i=nxt[i])if (e[i].v!=u)DFS(e[i].v,i);}void solve(){findroot(1,0);for (int t=1;t<=tot;t++){int u=rt[t];for (int i=head[u];i;i=nxt[i])if (!isrt[e[i].v])++son[u],Tree::dfs(e[i].v,u),F[u]+=F[e[i].v]+e[i].w;if (son[u]) F[u]/=son[u];}for (int i=1;i<=tot;i++){double p=0.5;int dis=0;for (int j=i%tot+1;j!=i;j=j%tot+1){dis+=w[j];if (j%tot+1==i) G[rt[i]]+=p*(dis+F[rt[j]]);else G[rt[i]]+=p*son[rt[j]]/(son[rt[j]]+1)*(dis+F[rt[j]]);p*=1.0/(son[rt[j]]+1);}p=0.5,dis=w[i];for (int j=(i==1? tot:i-1);j!=i;j=(j==1? tot:j-1)){if (i%tot+1==j) G[rt[i]]+=p*(dis+F[rt[j]]);else G[rt[i]]+=p*son[rt[j]]/(son[rt[j]]+1)*(dis+F[rt[j]]);p*=1.0/(son[rt[j]]+1);dis+=w[j];}}for (int t=1;t<=tot;t++){int u=rt[t];for (int i=head[u];i;i=nxt[i])if (!isrt[e[i].v])DFS(e[i].v,i);}double ans=0;for (int i=1;i<=n;i++) ans+=(isrt[i]+1)*G[i]/(son[i]+isrt[i]+1)+F[i]*son[i]/(son[i]+isrt[i]+1);printf("%.5f",ans/n); } } int main() {n=read(),m=read();for (int i=1;i<=m;i++){int u,v,w;u=read(),v=read(),w=read();addnode(u,v,w);addnode(v,u,w);}if (m==n-1) Tree::solve();else Circle::solve();return 0; }

總結

以上是生活随笔為你收集整理的【NOI2012】迷失游乐园【概率期望】【换根dp】【基环树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。