Normal

Luogu

IDLGP10632

Time1000ms

Memory512MB

DifficultyP7

图论点分治多项式Special JudgeO2优化期望快速数论变换 NTT

某天 WJMZBMR 学习了一个神奇的算法：树的点分治！这个算法的核心是这样的： ```cpp time = 0 Solve(Tree a) { time += a.size; if (a.size == 1) return; else { select x in a; delete a[x]; } } ``` ``` 消耗时间 = 0 Solve(树 a) 消耗时间 += a 的大小如果 a 中只有 1 个点退出否则在 a 中选一个点x 在 a 中删除点x ``` 那么 $a$ 变成了几个小一点的树，对每个小树递归调用 `Solve`。我们注意到的这个算法的时间复杂度跟选择的点 $x$ 是密切相关的，如果 $x$ 是树的重心，那么时间复杂度就是 $O(n \log n)$。 WJMZBMR 决定随机在 $a$ 中选择一个点作为 $x$，Sevenkplus 告诉他这样做的最坏复杂度是 $O(n^2)$，但是 WJMZBMR 就是不信，于是 Sevenkplus 花了几分钟写了一个程序证明了这一点，你也试试看吧。现在给你一颗树，你能告诉 WJMZBMR 他的算法需要的期望消耗时间吗（以给出的 `Solve` 函数中的为标准）？ ## Input 第一行一个整数 $n$，表示树的大小；接下来 $n-1$ 行每行两个整数 $a,b$，表示 $a$ 和 $b$ 之间有一条边。树的结点从 $0$ 开始编号。 ## Output 一行一个浮点数表示答案，并四舍五入到小数点后 $4$ 位。 [samples] ## Note 对于所有的数据，保证 $1\leq n\leq 30000$。

Samples

Input #1

3
0 1
1 2

Output #1

5.6667

API Response (JSON)

{
  "problem": {
    "name": "Normal",
    "description": {
      "content": "某天 WJMZBMR 学习了一个神奇的算法：树的点分治！ 这个算法的核心是这样的： ```cpp time = 0 Solve(Tree a) {   time += a.size;   if (a.size == 1) return;   else {     select x in a;     delete a[x];   } } ``` ``` 消耗时间 = 0 Solve(树 a)",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10632"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "某天 WJMZBMR 学习了一个神奇的算法：树的点分治！\n\n这个算法的核心是这样的：\n\n```cpp\ntime = 0\nSolve(Tree a) {\n  time += a.size;\n  if (a.size == 1) return;\n  else {\n    select x in a;\n    delete a[x];\n  }\n}\n```\n\n```\n消耗时间 = 0\nSolve(树 a)...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments