灰灰的笔记 / 【模板】树的直径(带权)
数据出锅
本题某些测试点数据可能有多解,目前还没处理。
题目描述
灰灰今天上体育课的时候,把他的OI笔记丢在了一棵树的根节点。但是想捡回来就没那么简单了;
已知每秒会有一页笔记被吹走,沿树上的边被吹到一个节点。已被吹走的笔记不会再被吹走;
下课了,风停了,灰灰现在需要把笔记捡回来,但他又 懒得动 没时间;
现在告诉你\(Q\)秒内的吹走情况,请你帮灰灰计算:灰灰走树上的哪一条连续路径可以捡到最多的笔记。
注:
- \(N\)秒后根节点笔记数为\(0\)
- 数据保证答案唯一
输入输出格式
输入格式
第一行两个整数\(M, Q\),分别表示边数与秒数,节点从\(0\)~\(M\)编号(根结点编号为\(0\))
接下来\(M\)行,每行两个整数\(u, v\),表示存在连接\(u, v\)的路径
接下来一行,\(Q\)个整数,第\(i\)个数表示第\(i\)份笔记被吹到的节点编号
输出格式
第一行两个整数\(u, 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, Q \leqslant 100\) |
5~8 | 无 | \(M, Q \leqslant 1000\) |
9~12 | 无 | \(M, Q \leqslant 10000\) |
13~20 | 无 | \(M, Q \leqslant 100000\) |
信息
- ID
- 1058
- 难度
- 9
- 分类
- (无)
- 标签
- (无)
- 递交数
- 9
- 已通过
- 1
- 通过率
- 11%
- 上传者
相关
在下列训练计划中: