| 题目名称 | 1038. [Squarefk] 树链剖分 |
|---|---|
| 输入输出 | treea.in/out |
| 难度等级 | ★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-08-22加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：27， 通过率：44.44% | ||||
 NewBee |
100 | 0.125 s | 2.22 MiB | C++ |
 哒哒哒哒哒！ |
100 | 0.152 s | 3.30 MiB | C++ |
 wangyucheng |
100 | 0.168 s | 1.57 MiB | C++ |
 raywzy |
100 | 0.188 s | 1.45 MiB | C++ |
 Sky_miner |
100 | 0.195 s | 1.55 MiB | C++ |
 _Itachi |
100 | 0.209 s | 10.30 MiB | C++ |
 Lunatic |
100 | 0.217 s | 2.55 MiB | Pascal |
 HouJikan |
100 | 0.263 s | 3.12 MiB | C++ |
 sk_code |
100 | 0.344 s | 4.62 MiB | C++ |
 Magic_Sheep |
100 | 0.361 s | 0.87 MiB | C++ |
| 关于 树链剖分 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
画一画答案十分明显。。只需要统计有用儿子数量即可
| ||||
-
树链剖分
【问题描述】
其实，本题和树链剖分没有关系。
作为一名OIer，ZYN和LHC自然要好好利用暑假学习算法、数据结构。某一
天，他们在一起研究树链剖分，被FK看到了。FK决定不懂装懂，问了他们一个
很奇怪的问题：给你们一棵树，能够拆成的最小的链数是多少？
链的定义：一个由X个点和X-1条边组成的连通块，注意X≥1，每个点的
度数≤2。
拆的要求：将原图中的一些边删去，使得每个点属于一条链。
ZYN笑了笑：“这很简单么。。。只要。。。只要。。。”LHC随声附和“对！
对！”，可不久两人都陷入了沉思。FK因为难倒了他们而窃喜，实际上他自己
也不会做。那么你能帮帮这三个悲催的人么。
【输入格式】
从文件tree.in中读入数据。
第1行有1个数N，表示树的节点的个数。
第2行到第N行，每行两个数X、Y，表示在树上点X与Y之间有边相连。
【输出格式】
输出到文件tree.out中。
输出1行，包含1个数，表示最少能拆成的链数。
【样例输入】
4
1 2
1 3
1 4
【样例输出】
2
【样例解释】
两条链分别是：2-1-3，4
【数据范围】
对于30%数据，N≤10
对于60%数据，N≤300
对于100%数据，N≤100000