TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P7011
  • Problem
  • P7011狡兔三窟
    Limits : Time Limit : - MS   Memory Limit : 262144 KB
    Judgment Tips : 2s,256m
    Description

    nodgd发现了野生的兔子,但转眼间兔子就已经钻进地洞。

    野外是一个树形结构, \(n\) 个节点编号分别为 $1,2,\cdots,n$ , \(n-1\) 条边第 \(i\) 条边连接节点 \(x_i,y_i\) ,每条边长度都是 $1$ 。

    根据nodgd多年的研究,兔子的洞穴有且仅有一条主要通道,主要通道一定是树上的一条简单路径(长度可能为 $0$ )。兔子依靠洞口进出,为了方便,每个洞口到主要通道的距离总是不超过 $1$ 。

    为了抓到野生兔子,nodgd找遍所有节点发现了 \(k\) 个洞口,分布在节点 \(p_1,p_2,\cdots,p_k\) 。nodgd想要通过这些信息推测兔子洞穴的主要通道可能在哪里,但问题在于节点太多了难以手动计算,所以请你写个程序帮忙计算。

    Input Format

    第一行两个整数 \(n,q\) ,表示节点数和询问的次数。

    接下来 \(n-1\) 行,每行两个整数 \(x_i,y_i\) 表示一条边。

    接下来 \(q\) 行每行一个询问。第一个整数 \(k\) 表示洞口的数量,接下来$k$ 个互不相同的整数 \(p_1,\cdots,p_k\)

    Output Format

    每次询问输出一行。

    • 如果存在符合要求的主要通道,先输出 YES 然后再输出两个整数,表示主要通道的两个端点的节点编号,中间用空格间隔。如果有很多条符合要求的主要通道,你可以随便输出一种。
    • 如果不存在符合要求的主要通道,输出 NO
    Sample Input

    10 5
    1 2
    2 3
    1 4
    4 5
    1 6
    6 7
    7 8
    6 9
    7 10
    10 1 2 3 4 5 6 7 8 9 10
    3 3 5 7
    3 3 4 10
    3 2 4 6
    4 2 4 9 10

    Sample Output

    NO
    NO
    YES 3 10
    YES 1 1
    YES 1 7

    Hint

    对于所有测试数据, $1\leq n,q,\sum k\leq 2\cdot10^5$ , $1\leq x_i,y_i,k,p_i\leq n$ 。

    每个子任务不捆绑,分值均匀分布在每个测试点上。

    子任务 \(\qquad\) 分值 \(\qquad\) \(n\leq\) \(\qquad\) \(q\leq\) \(\qquad\) \(\sum k\leq\) \(\qquad\) 其他限制
    $1$ $10$ $50$ $10$ $200$
    $2$ $15$ $200$ $200$ $200$
    $3$ $10$ $2\ 000$ $2\ 000$ $2\ 000$ 每次询问 \(k\leq 3\)
    $4$ $15$ $2\ 000$ $2\ 000$ $2\ 000$
    $5$ $4$ $200\ 000$ $200\ 000$ $200\ 000$ 每条树边 \(y_i=x_i+1\)
    $6$ $4$ $200\ 000$ $200\ 000$ $200\ 000$ 每次询问 \(k\leq 2\)
    $7$ $12$ $200\ 000$ $200\ 000$ $200\ 000$ 每次询问 \(k\leq 3\)
    $8$ $10$ $200\ 000$ $200\ 000$ $200\ 000$ 每次询问 \(k\leq 5\)
    $9$ $20$ $200\ 000$ $200\ 000$ $200\ 000$

    Source  nodgd