传送门

考虑每一对幸运点对的贡献，假设有 \(v\) 对

一共可以选择 \(x\) 个点，总共 \(n\) 个点

那么答案就是

统计点对个数就好了

Q: 一道点分治入门题目为什么要写长链剖分

A: 因为太久没有写过了有点忘了...

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn(1e5 + 5);

int first[maxn], cnt, n, m, lucky[20], tmp[maxn], *id, *f[maxn], son[maxn], len[maxn];

ll ans;

double ret;

struct Edge {

	int to, next;

} edge[maxn];

inline void Add(int u, int v) {

	edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;

	edge[cnt] = (Edge){u, first[v]}, first[v] = cnt++;

}

void Dfs1(int u, int ff) {

	int e, v;

	for (e = first[u]; ~e; e = edge[e].next)

		if ((v = edge[e].to) ^ ff) Dfs1(v, u), son[u] = len[v] > len[son[u]] ? v : son[u];

	len[u] = len[son[u]] + 1;

}

void Dfs2(int u, int ff) {

	int e, v, i, j;

	f[u][0] = 1;

	if (son[u]) f[son[u]] = f[u] + 1, Dfs2(son[u], u);

	for (i = 1; i <= m; ++i) if (lucky[i] < len[u]) ans += f[u][lucky[i]];

	for (e = first[u]; ~e; e = edge[e].next)

		if (((v = edge[e].to) ^ ff) && (v ^ son[u])) {

			f[v] = id, id += len[v];

			Dfs2(v, u);

			for (i = 1; i <= m; ++i)

				for (j = 0; j < len[v] && j < lucky[i]; ++j)

					if (lucky[i] - j - 1 < len[u]) ans += (ll)f[u][lucky[i] - j - 1] * f[v][j];

			for (i = 1; i <= len[v]; ++i) f[u][i] += f[v][i - 1];

		}

}

int main() {

	int i, n1, n2, n3, u, v;

	memset(first, -1, sizeof(first));

	scanf("%d%d", &n, &m);

	for (i = 1; i <= m; ++i) scanf("%d", &lucky[i]);

	n1 = 0, n2 = 0, n3 = 0;

	for (i = 1; i <= n; ++i)

		if (i % 3 == 1) ++n1;

		else if (i % 3 == 2) ++n2;

		else ++n3;

	for (i = 1; i < n; ++i) scanf("%d%d", &u, &v), Add(u, v);

	Dfs1(1, 0), f[1] = id = tmp, id += len[1], Dfs2(1, 0);

	ret = 1.0 * ans / (1.0 * (n - 1) * n);

	printf("%.2lf\n%.2lf\n%.2lf\n", ret * n1 * (n1 - 1), ret * n2 * (n2 - 1), ret * n3 * (n3 - 1));

	return 0;

}