#2542. 「PKUWC2018」随机游走

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

题目描述

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

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

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

答案对 998244353998244353 取模。

输入格式

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

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

接下来 QQ 行,每行第一个数 kk 表示集合大小,接下来 kk 个互不相同的数表示集合 SS

输出格式

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

样例

样例输入

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

样例解释

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

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

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

数据范围与提示

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

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

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

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

对于 100%100\% 的数据,有 1n181\leq n\leq 181Q50001\leq Q\leq 50001kn1\leq k\leq n