F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5479. -- tree

5479: tree

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 116  Solved: 19
[Submit][Status][Discuss]

Description

给出一棵树,根节点为1
给出两个集合,集合由树上节点组成
从两个集合分别选出一个元素,求其LCA
问LCA的最大深度是多少

Input

第一行给出数据组数T
对于每组数据
第一行给出N,M,代表树的节点个数及询问次数
接下来N-1行,每行两个正整数u,v,表示u,v之间有边
接下来2M行,每两个表示一个询问
询问的第一行,第一行正整数a代表集合A中元素个数
接下来a个正整数,表示集合中的节点
询问的第二行,第一行正整数b代表集合B中元素个数
接下来b个正整数,表示集合中的节点
T<=5,N,M<=100000
sigma(a)+sigma(b)<=200000
a,b<=N

Output

对于每个询问,一行一个整数表示结果

Sample Input

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

Sample Output

3
4
2

HINT

Source

[Submit][Status][Discuss]

HOME Back