loj#P3066. 「ROI 2016 Day2」快递

「ROI 2016 Day2」快递

题目描述

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

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

输入格式

第一行:n,kn,k
第二行:n1n-1 个整数 f2fnf_2\ldots f_nfif_i 表示 ii 号结点与 fif_i 号结点相连。
接下来 kk 行:kk 条路径的端点。

输出格式

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

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

数据范围与提示

对于所有数据,1pi<i1\le p_i<i,保证路径端点 1ai,bin,aibi1\le a_i,b_i\le n,a_i\neq b_i

子任务编号 分值 2n2 ⩽ n ⩽ 2k2 ⩽ k ⩽ 附加条件
1 29 100100
2 12 40004000 10001000
3 7 10510^5
4 8 50005000
5 10 5000050000 路径长度小于等于 2020
6 12 对于任意路径,路径上其中
一点一定是另一点的祖先
7  12 
8 10 21052\cdot 10^5