Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom11月前

07/31
20:25
LCA

[bzoj 1787] [Ahoi2008]Meet 紧急集合

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

17871

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

17872

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

17873

♦♦♦♦♦♦   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   ♦♦♦♦♦♦

17874

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

可以发现,选择的那个点一定是对询问的三个点两两做lca以后,三个lca中深度比较大的那一个,也就是除开两个相同lca后剩下的一个

c++:

pascal:

 

[bzoj 1787] [Ahoi2008]Meet 紧急集合