【bzoj1787】[Ahoi2008]Meet 紧急集合

2014年5月7日3,1582

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分别计算取最优

 

  • Ccccy!2016年1月16日 上午9:44 回复

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

    #1  
    • hzwer2016年1月16日 下午2:16 回复
      admin

      就几种情况,都考虑一下就能得出结论?

      #11