# Codeforces 1087D - Minimum Diameter Tree

## 题解链接

https://lucien.ink

## 题目链接

http://codeforces.com/contest/1087/problem/D

## 实现

https://pasteme.cn/2804

#include <bits/stdc++.h>
const int maxn = int(2e5) + 7, maxm = int(4e5) + 7;
struct Lca {
struct { int next, to, val; } edge[maxm]{};
void addedge(int u, int v) {
}
explicit Lca() {
cnt = 0;
memset(up, 0xff, sizeof(up));
}
void init(int n) {
std::queue<int> que;
que.emplace(dep[1] = 1);
int u, v;
while (!que.empty()) {
u = que.front(), que.pop();
for (int i = head[u]; ~i; i = edge[i].next) {
v = edge[i].to;
if (dep[v]) continue ;
up[v][0] = u, dep[v] = dep[u] + 1, que.push(v);
}
}
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= n; i++)
if (~up[i][j - 1])
up[i][j] = up[up[i][j - 1]][j - 1];
}
int query(int u, int v) {
if (dep[u] < dep[v]) std::swap(u, v);
int tmp = dep[u] - dep[v];
for (int j = 0; tmp; j++)
if (tmp & (1 << j)) tmp ^= (1 << j), u = up[u][j];
if (u == v) return v;
for (int j = 20; j >= 0; j--) {
if (up[u][j] != up[v][j]) {
u = up[u][j], v = up[v][j];
}
}
return up[u][0];
}
} lca;
int deg[maxn], n, s, leaf[maxn], cnt;
int main() {
std::scanf("%d%d", &n, &s);
if (n == 2) return 0 * std::printf("%d\n", s);
for (int i = 1, u, v; i < n; i++) {
std::scanf("%d%d", &u, &v);
deg[u]++, deg[v]++;
}
lca.init(n);
for (int i = 1; i <= n; i++) if (deg[i] == 1) leaf[++cnt] = i;
int pre = leaf[1], min = 0x3f3f3f3f, min_dep = lca.dep[leaf[1]];
for (int i = 2; i <= cnt; i++) {
pre = lca.query(pre, leaf[i]);
min = std::min(min_dep + lca.dep[leaf[i]] - lca.dep[pre] * 2, min);
min_dep = std::min(min_dep, lca.dep[leaf[i]]);
}
min >>= 1;
printf("%.15lf\n", double(s) / double(min * cnt) * min * 2);
return 0;
}