loj#P3066. 「ROI 2016 Day2」快递
「ROI 2016 Day2」快递
题目描述
译自 ROI 2016 Day2 T3. Курьерская служба
给一棵包含 个结点的树,结点分别编为 号。
树上有 条简单路径,路径的编号分别为 。给出这些路径的端点 。
我们把「两条路径中的公共结点数 」称作两路径的重合长度。
试求:哪两条简单路径的重合长度最大,并给出最大重合长度。
输入格式
第一行:
第二行: 个整数 , 表示 号结点与 号结点相连。
接下来 行: 条路径的端点。
输出格式
第一行:最大重合长度
第二行:两条边的编号,用一个空格隔开,可以以任意顺序输出。
4 2
1 2 2
1 3
1 4
1
2 1
4 2
1 2 3
1 2
3 4
0
1 2
7 3
1 2 2 4 5 5
1 3
3 7
6 1
2
2 3
4 3
1 2 3
1 4
4 1
1 4
3
2 1
数据范围与提示
对于所有数据,,保证路径端点 。
子任务编号 | 分值 | 附加条件 | ||
---|---|---|---|---|
1 | 29 | |||
2 | 12 | |||
3 | 7 | |||
4 | 8 | |||
5 | 10 | 路径长度小于等于 | ||
6 | 12 | 对于任意路径,路径上其中 一点一定是另一点的祖先 |
||
7 | 12 | |||
8 | 10 |