#P4281. [AHOI2008] 紧急集合 / 聚会

    ID: 5046 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2008倍增各省省选安徽最近公共祖先,LCA树链剖分,树剖

[AHOI2008] 紧急集合 / 聚会

题目描述

欢乐岛上有个非常好玩的游戏,叫做“紧急集合”。在岛上分散有 nn 个等待点,有 n1n-1 条道路连接着它们,每一条道路都连接某两个等待点,且通过这些道路可以走遍所有的等待点,通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组,开始的时候,所有人员均任意分散在各个等待点上(每个点同时允许多个人等待),每个人均带有足够多的游戏币(用于支付使用道路的花费)、地图(标明等待点之间道路连接的情况)以及对话机(用于和同组的成员联系)。当集合号吹响后,每组成员之间迅速联系,了解到自己组所有成员所在的等待点后,迅速在 nn 个等待点中确定一个集结点,组内所有成员将在该集合点集合,集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏,由你来选择集合点,聪明的你能够完成这个任务,帮助小可可赢得游戏吗?

输入格式

第一行两个正整数 nnmm,分别表示等待点的个数(等待点也从 11nn 进行编号)和获奖所需要完成集合的次数。

随后 n1n-1 行,每行两个正整数 a,ba,b,表示编号为 aa 和编号为 bb 的等待点之间有一条路。

随后 mm 行,每行用三个正整数 x,y,zx,y,z,表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式

输出共 mm 行,每行两个用空格隔开的整数 p,cp,c。其中第 ii 行表示第 ii 次集合点选择在编号为 pp 的等待点,集合总共的花费是 cc 个游戏币。

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



提示

对于 40%40\% 的数据,n2×103n\leq2\times10^3m2×103m\leq2\times 10^3

对于 100%100\% 的数据,1x,y,zn5×1051\leq x,y,z\leq n\leq 5\times10^51m5×1051\leq m\leq 5\times 10^5