[POI 2004] SZN

Luogu
IDLGP8384
Time1000ms
Memory128MB
DifficultyP5
2004POI(波兰)
$\text{String-Toys joint-stock}$ 公司需要你帮他们解决一个问题。 他们想制造一个没有环的连通图模型,每个图都是由一些顶点和特定数量的边构成。每个顶点都可以连向许多的其他顶点。一个图是连通且无环的,图是由许多的线做成的。一条线是一条连接图中两个顶点之间的路径。 由于一些技术原因,两条线之间不能有重叠的部分,要保证图中任意一条边都被且仅被一条线所覆盖。 做一个这样的图的模型的费用取决于用了多少条线以及最长的那条的长度(每条边的长度都为 $1$ )。 现在给你对应的图,请你编写一个程序,求出最少能用多少条线以及在用最少线的情况下最长的那根线最短可以为多少。 ## Input 第一行仅包含一个数 $n$ ,表示顶点的总数。顶点从 $1$ 到 $n$ 进行编号。 接下来的 $n - 1$ 行描述这些边,每行两个数 $a$ 和 $b$,表示顶点 $a$ 和顶点 $b$ 之间有一条边。 ## Output 输出两个数,最少用多少条线以及在用最少线的情况下最长线最短可以为多少. [samples] ## Note 对于 $100$ % 的数据:$2 \le n \le 10000,1 \le a,b \le n$ 。 样例解释: ![](https://cdn.luogu.com.cn/upload/image_hosting/00d4scv1.png)
Samples
Input #1
9
7 8
4 5
5 6
1 2
3 2
9 8
2 5
5 8
Output #1
4 2
API Response (JSON)
{
  "problem": {
    "name": "[POI 2004] SZN",
    "description": {
      "content": "$\\text{String-Toys joint-stock}$ 公司需要你帮他们解决一个问题。 他们想制造一个没有环的连通图模型,每个图都是由一些顶点和特定数量的边构成。每个顶点都可以连向许多的其他顶点。一个图是连通且无环的,图是由许多的线做成的。一条线是一条连接图中两个顶点之间的路径。 由于一些技术原因,两条线之间不能有重叠的部分,要保证图中任意一条边都被且仅被一条线所覆盖。 做一个这样",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8384"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$\\text{String-Toys joint-stock}$ 公司需要你帮他们解决一个问题。\n\n他们想制造一个没有环的连通图模型,每个图都是由一些顶点和特定数量的边构成。每个顶点都可以连向许多的其他顶点。一个图是连通且无环的,图是由许多的线做成的。一条线是一条连接图中两个顶点之间的路径。\n\n由于一些技术原因,两条线之间不能有重叠的部分,要保证图中任意一条边都被且仅被一条线所覆盖。\n\n做一个这样...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments