树上的路灯很社恐
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
有一棵 个点的树,点编号为 到 。
树上每个点都有一盏路灯。两盏路灯之间的社交距离定义为它们所在点之间简单路径的边数。
现在,路灯们只愿意和距离为偶数的路灯组成"夜间摸鱼小组"。请问有多少对不同的路灯 满足 且 与 的距离为偶数?
Format
Input
第一行一个整数 。
接下来 行,每行两个整数 ,表示树上有一条连接 和 的边。
输入保证给出的是一棵树。
Output
输出一行一个整数,表示距离为偶数的点对数量。
Samples
5
1 2
1 3
3 4
3 5
4
Note
样例说明:
以 为根时,深度为偶数的点有 ,深度为奇数的点有 。
距离为偶数的点对为:共 对。
2026江南程序设计竞赛联盟暑期多校训练-摸底赛(重现)
- Status
- Done
- Rule
- XCPC
- Problem
- 11
- Start at
- 2026-10-14 13:45
- End at
- 2026-10-14 17:45
- Duration
- 4 hour(s)
- Host
- Partic.
- 2