題意 ：

• 給定一棵n個點的樹，A在1號點，B的位置在2-n中均勻隨機，A不知道B的位置，現在A要去找B，每秒可以走到一個相鄰點，求在最優策略（$optimal$ $strategy$）下的期望時間

思路 ：

• 等概率出現，因此直接把所有（2-n）結點需要的次數累加后除以（$n?1$）
• 先假設走的路徑是一個歐拉遍歷。容易發現交換一個點的兩顆子樹答案不變
• 有了上述結論之后，容易證明最優解確實是一個歐拉遍歷，也就是不會半途返回，
• 按任意順序DFS即可，時間復雜度$O(n)$
• 樹的遍歷只要傳入父節點即可，不需要vis數組
• dfs的方案就是每次回溯回來后cnt還是加一，這樣就能構造“走回”的效果；
• 還要注意一開始cnt初始化為-1，因為在第一個點是第0s

#include <iostream> #include <vector> #define pb push_backusing namespace std;const int N = 110;int n; vector<int> g[N]; int cnt = -1, ans;void dfs(int u, int fa) {cnt ++ ;ans += cnt;for (int i = 0; i < g[u].size(); i ++ ){int v = g[u][i];if (v == fa) continue;dfs(v, u);cnt ++ ;} }int main() {int _ = 1;scanf("%d", &_);while (_ -- ){scanf("%d", &n);for (int i = 1; i <= n; i ++ ) g[i].clear();cnt = -1, ans = 0;for (int i = 0, u, v; i < n - 1; i ++ ){scanf("%d%d", &u, &v);g[u].pb(v), g[v].pb(u);}dfs(1, 0);printf("%.10lf\n", ans * 1.0 / (n - 1));} }

總結

以上是生活随笔為你收集整理的Search For Mafuyu dfs，树的遍历，期望（济南）的全部內容，希望文章能夠幫你解決所遇到的問題。

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