树上两点期望距离

Posted on |

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;
}