「BZOJ1787」[Ahoi2008] Meet 紧急集合

2014年5月7日3,7682

Description

Input

Output

Sample Input

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

Sample Output


5 2
2 5
4 1
6 0

HINT

题解

忘记换行搞半天我擦咧

求三个结点到一个结点距离之和最小的结点以及距离和

求出两两lca,其中有两个相同,答案则为另一个,画画图就可以理解

或者将三个lca分别计算取最优

 

说点什么

提醒
avatar
Ccccy!
Ccccy!

黄学长,第一个方法画图是明白了的确如此,但是为什么就是另外一个呢?