#P1194. 随机游走

随机游走

题目描述

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

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

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

答案对 998244353998244353 取模。

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

3 5 1
1 2
2 3
1 1
1 3
2 2 3
3 1 2 3
2 1 2

样例输出 #1

0
4
4
4
1

提示

对于 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