Problem
求树上两点之间的期望距离。
Solution
设d[i]为i节点的度数。
fa[i]为i节点的父亲。
我们对于两种不同的走法分别考虑。
Part1：儿子到父亲
设此时期望步数为f[i]。
显然，只会有两种情况：
1.直接一步走到父亲。
2.先走到自己的儿子，再走回自己，再走到父亲。
对于情况1.概率为$ \frac{1}{d[i]}$ ,步数为1，期望为 $ \frac{1}{d[i]}$。
对于情况2.分步考虑:
\(1^{st}\) :走到儿子，发生概率为 $ \frac{d[i]-1}{d[i]}$ ,步数为1，期望为$ \frac{d[i]-1}{d[i]}$
\(2^{nd}\) :儿子走到自己，期望为 $ \sum\limits_{j∈i的儿子}\frac {f[j]}{d[i]}$
\(3^{rd}\) :自己走到父亲，期望为 $ \frac{(d[i]-1)×f[i]}{d[i]}$
综上，我们有：\[ f[i]=\frac{1+\sum\limits_{j∈i的儿子}{(f[j]+f[i]+1)}}{d[i]} \] 移项化简之后我们得到：\[ f[i]=d[i]+\sum\limits_{j∈i的儿子}f[j] \]
Part2:父亲到儿子。
设此时期望步数为g[i]。
那么，我们有三种情况
1.直接跳到指定的儿子。
2.跳到父亲的父亲，再回到该点，再到达指定儿子。
3.跳到另一个儿子，再跳回来，再到达指定儿子。
还是像f数组一样讨论即可。\[ g[i] = \frac{1+(1+g[fa[i]]+g[i])+\sum\limits_{son!=i}{(1+f[son]+g[i])}}{d[i]} \] 化简后：\[ g[i]=g[fa[i]]+d[fa[i]]+\sum\limits_{son!=i}f[son] \] 好了，两种情况都考虑完之后，就可以算距离了。
距离计算
对于给定的u--->v的路径，我们可以拆成两条：\(u \to LCA\); \(LCA\to v\)。
其中对于第一条路径，肯定都是向上走，另一条则是向下的。
所以：\[ ans=\sum\limits_{i∈(u\to LCA)}f[i]+\sum\limits_{i∈(u\to LCA)}g[i]-f[LCA]-g[LCA] \] 记一个树上前缀和即可。
Code
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define fst first
#define snd second
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
inline int read(){
int res = 0, fl = 1;
char r = getchar();
for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1;
for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48;
return res * fl;
}
typedef long long LL;
typedef pair<int, int> pii;
const int Maxn = 5e4 + 10;
int fa[Maxn][17], dep[Maxn];
LL up[Maxn], down[Maxn];
vector <int> g[Maxn];
void clean(int n){
for (int i = 1; i <= n; ++i) g[i].clear();
}
void dfsu(int now, int pa){
up[now] = g[now].size();
for (int i = g[now].size() - 1; i >= 0; --i){
int nxt = g[now][i];
if(nxt == pa) continue;
dfsu(nxt, now);
up[now] += up[nxt];
}
}
void dfsd(int now, int pa, int ppa){
down[now] = g[pa].size() + down[pa];
LL sum = 0;
if(now != 1) down[now] += up[pa] - up[now] - g[pa].size();
for (int i = g[now].size() - 1; i >= 0; --i){
int nxt = g[now][i];
if(nxt == pa) continue;
dfsd(nxt, now, pa);
}
}
void dfs(int now,int pa){
up[now] += up[pa];
down[now] += down[pa];
fa[now][0] = pa, dep[now] = dep[pa] + 1;
for (int i = 1; i <= 16; ++i) fa[now][i] = fa[fa[now][i - 1]][i - 1];
for (int i = g[now].size() - 1; i >= 0; --i){
int nxt = g[now][i];
if(nxt == pa) continue;
dfs(nxt, now);
}
}
int LCA(int u,int v){
if(dep[u] < dep[v]) swap(u, v);
for (int i = 16; i >= 0; --i) if(dep[fa[u][i]] >= dep[v]) u = fa[u][i];
if(u == v) return u;
for (int i = 16; i >= 0; --i) if(fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];
return fa[u][0];
}
void solve(){
int n = read();
for (int i = 1; i < n; ++i){
int x= read() + 1, y = read() + 1;
g[x].push_back(y);
g[y].push_back(x);
}
dfsu(1, 0);
dfsd(1, 0, 0);
dfs(1, 0);
int Q = read();
for (int i = 1; i <= Q; ++i){
int p = read(), now = read() + 1;
LL ans = 0;
for (int j = 1; j <= p; ++j){
int lst = now;
now = read() + 1;
int Lca = LCA(now, lst);
ans += up[lst] - up[Lca] + down[now] - down[Lca];
}
printf("%lld.0000\n",ans);
}
clean(n);
}
int main()
{
freopen("C.in", "r", stdin);
freopen("C.out", "w", stdout);
int t = read();
while(t--) {
solve();
printf("\n");
}
return 0;
}
转载于:https://www.cnblogs.com/LZYcaiji/p/10397875.html
