树上两点期望距离

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]}$

综上,我们有:

移项化简之后我们得到:

Part2:父亲到儿子。

设此时期望步数为g[i]。

那么,我们有三种情况

1.直接跳到指定的儿子。

2.跳到父亲的父亲,再回到该点,再到达指定儿子。

3.跳到另一个儿子,再跳回来,再到达指定儿子。

还是像f数组一样讨论即可。

化简后:

好了,两种情况都考虑完之后,就可以算距离了。

距离计算

对于给定的u—->v的路径,我们可以拆成两条:$u \to LCA$; $LCA\to v$。

其中对于第一条路径,肯定都是向上走,另一条则是向下的。

所以:

记一个树上前缀和即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#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;
}