#2542. 「PKUWC2018」随机游走

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: l0nl1f3

题目描述

给定一棵 n 个结点的树,你从点 x 出发,每次等概率随机选择一条与所在点相邻的边走过去。

Q 次询问,每次询问给定一个集合 S ,求如果从 x 出发一直随机游走,直到点集 S 中所有点都至少经过一次的话,期望游走几步。

特别地,点 x (即起点)视为一开始就被经过了一次。

答案对 998244353 取模。

输入格式

第一行三个正整数 n,Q,x

接下来 n-1 行,每行两个正整数 (u,v) 描述一条树边。

接下来 Q 行,每行第一个数 k 表示集合大小,接下来 k 个互不相同的数表示集合 S

输出格式

输出 Q 行,每行一个非负整数表示答案。

样例

样例输入

3 5 1
1 2
2 3
1 1
1 3
2 2 3
3 1 2 3
2 1 2
样例输出
0
4
4
4
1

样例解释

样例给的树是一条长度为 3 的链,且起点是链的一端,所以答案只跟最远的那个点有关。

当最远的点是 2 时,显然只需要 1 步就行了。

当最远的点是 3 时,通过计算可得期望 4 步到达。

数据范围与提示

对于 20\% 的数据,有 1\leq n,Q\leq 5

另有 10\% 的数据,满足给定的树是一条链。

另有 10\% 的数据,满足对于所有询问有 k=1

另有 30\% 的数据,满足 1\leq n\leq 10 ,Q=1

对于 100\% 的数据,有 1\leq n\leq 18 1\leq Q\leq 5000 1\leq k\leq n