列表

详情

NC53400. 快递

描述

译自 ROI 2016 Day2 T3. Курьерская служба

给一棵包含n个结点的树，结点分别编为号。
树上有k条简单路径，路径的编号分别为。给出这些路径的端点a_i,b_i。
我们把「两条路径中的公共结点数-1」称作两路径的重合长度。
试求：哪两条简单路径的重合长度最大，并给出最大重合长度。

输入描述

第一行：n,k
第二行：n-1个整数，f_i表示i号结点与f_i号结点相连。
接下来k行：k条路径的端点。

输出描述

第一行：最大重合长度
第二行：两条边的编号，用一个空格隔开，可以以任意顺序输出。

示例1

输入: 

4 2
1 2 2
1 3
1 4

输出: 

1
2 1

示例2

输入: 

4 2
1 2 3
1 2
3 4

输出: 

0
1 2

示例3

输入: 

7 3
1 2 2 4 5 5
1 3
3 7
6 1

输出: 

2
2 3

说明:

示例4

输入: 

4 3
1 2 3
1 4
4 1
1 4

输出: 

3
2 1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

上一题

© 2024 nowcoder.com