cf提交记录

$Code$

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
const int M = 2 * N;

int n;
int he[N], ed[M], ne[M], idx;
int passed[N];
double sum; // 总路程
int ways; // 总路径数

void add(int a, int b) {
	ed[idx] = b, ne[idx] = he[a], he[a] = idx ++;
}

void dfs(int u, int rode) { // u: 当前节点编号，rode: 走的路程
	int went = 0;
	for (int i = he[u]; i != -1; i = ne[i]) {
		int j = ed[i];
		if (passed[j] == 0) { // 这里没来过
			went = 1;
			passed[j] = 1;
			dfs(j, rode + 1);
			passed[j] = 0;
		}
	}
	if (!went) { // 如果u点是路的尽头，那么总路程sum += 这段路的长度，总路径数 ++;
		sum += rode;
		ways ++;
	}
}

int main() {
	
	memset(he, -1, sizeof he);

	cin >> n;
	
	for (int i = 1; i <= n - 1; i ++) {
		int a, b; cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	
	passed[1] = 1; // 标记1节点来过
	dfs(1, 0); // 从1节点开始dfs

	cout << sum / ways << endl; // 总路程 / 总路径数
	return 0;
}