小 W 有一棵
- 给定两个点
和 ,首先对于 到 路径上的所有点 (包含 和 ),你要将与 相连的所有边变为轻边。然后再将 到 路径上包含的所有边变为重边。 - 给定两个点
和 ,你需要计算当前 到 的路径上一共包含多少条重边。
输入格式
本题有多组数据,输入数据第一行一个正整数
对于每组数据: 第一行包含两个整数
接下来
接下来
数据保证
输出格式
对于每一次第
样例一
input
1 7 7 1 2 1 3 3 4 3 5 3 6 6 7 1 1 7 2 1 4 2 2 7 1 1 5 2 2 7 1 2 1 2 1 7
output
1 3 2 1
explanation
第 1 次操作后,重边有:
第 2 次操作,包含的重边有:
第 3 次操作,包含的重边有:
第 4 次操作,首先
第 5 次操作,包含的重边有:
第 6 次操作,首先
第 7 次操作,包含的重边有:
样例二
见附加文件的 ex_edge2.in
与 ex_edge2.ans
。
该样例约束与测试点
样例三
见附加文件的 ex_edge3.in
与 ex_edge3.ans
。
该样例约束与测试点
样例四
见附加文件的 ex_edge4.in
与 ex_edge4.ans
。
该样例约束与测试点
样例五
见附加文件的 ex_edge5.in
与 ex_edge5.ans
。
该样例约束与测试点
测试点约束
对于所有测试数据,有
测试点编号 | 特殊性质 | |
---|---|---|
无 | ||
A, B | ||
A | ||
B | ||
无 | ||
特殊性质 A:树的形态是一条链。
特殊性质 B:第
时间限制:
空间限制: