[JLOI2014] 松鼠的新家
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.
题目描述
松鼠的新家是一棵树，前几天刚刚装修了新家，新家有 个房间，并且有 根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。
松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去 ，再去 ，……，最后到 ，去参观新家。可是这样会导致重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。
维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。
因为松鼠参观指南上的最后一个房间 是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。
输入格式
第一行一个正整数 ，表示房间个数第二行 个正整数，依次描述 。
接下来 行，每行两个正整数 ，表示标号 和 的两个房间之间有树枝相连。
输出格式
一共 行，第 行输出标号为 的房间至少需要放多少个糖果，才能让维尼有糖果吃。
样例 #1
样例输入 #1
5
1 4 5 3 2
1 2
2 4
2 3
4 5
样例输出 #1
1
2
1
2
1
提示
对于全部的数据，，。
北辰OI俱乐部算法提高班：图论专题
- Status
- Done
- Problem
- 23
- Open Since
- 2023-11-25 0:00
- Deadline
- 2024-12-31 23:59
- Extension
- 24 hour(s)
