灰灰的笔记 / 【模板】树的直径(带权)

灰灰的笔记 / 【模板】树的直径(带权)

数据出锅

本题某些测试点数据可能有多解,目前还没处理。

题目描述

灰灰今天上体育课的时候,把他的OI笔记丢在了一棵树的根节点。但是想捡回来就没那么简单了;
已知每秒会有一页笔记被吹走,沿树上的边被吹到一个节点。已被吹走的笔记不会再被吹走;
下课了,风停了,灰灰现在需要把笔记捡回来,但他又 懒得动 没时间;
现在告诉你QQ秒内的吹走情况,请你帮灰灰计算:灰灰走树上的哪一条连续路径可以捡到最多的笔记。

注:

  • NN秒后根节点笔记数为00
  • 数据保证答案唯一

输入输出格式

输入格式

第一行两个整数M,QM, Q,分别表示边数与秒数,节点从00~MM编号(根结点编号为00
接下来MM行,每行两个整数u,vu, v,表示存在连接u,vu, v的路径
接下来一行,QQ个整数,第ii个数表示第ii份笔记被吹到的节点编号

输出格式

第一行两个整数u,vu, v表示最优路径的两个端点,编号小的在前
第二行一个整数,表示灰灰能捡到的最多笔记数

样例

输入

6 16
0 1
1 2
1 3
0 4
3 5
4 6
2 4 1 3 6 1 5 4 6 4 1 6 1 4 6 4

输出

5 6
15

样例解释


如图,走橙色路径能捡到的笔记数量最多

数据范围

测试点编号 特殊性质 数据规模
1~4 M,Q100M, Q \leqslant 100
5~8 M,Q1000M, Q \leqslant 1000
9~12 M,Q10000M, Q \leqslant 10000
13~20 M,Q100000M, Q \leqslant 100000

信息

ID
1058
难度
9
分类
(无)
标签
(无)
递交数
9
已通过
1
通过率
11%
上传者

相关

在下列训练计划中:

模板 | Templates