Description：

一棵树上从点 $x$ 出发，每次等概率随机选择一条与所在点相邻的边走过去。 $Q$ 次询问，每次询问给定一个集合，求如果从 $x$ 出发一直随机游走，直到点集 $S$ 中所有点都至少经过一次的话，期望游走几步。

$1\leqslant n\leqslant 18,1\leqslant Q\leqslant 5000$

Solution：

首先所有点都经过很不好求，我们可以用 $\min-\max$ 容斥转化为至少经过一次集合内的点的期望，那么有： $$ \begin{align} f[i]&=0&i\in S\\ f[i]&=1+\frac1df[fa[i]]+\frac 1d\sum_{j\in ch[i]}f[j]&i\notin S \end{align} $$ 于是树上消元： $$ f[i]=\frac1d f[fa[i]]+1+\frac 1d\sum_{j\in ch[i]}(k_jf[i]+b_j)\Rightarrow f[i]=\frac1{d-\sum_{j\in ch[i]}k_j}f[fa[i]]+\frac{d+\sum_{j\in ch[i]}b_j}{d-\sum_{j\in ch[i]}k_j} $$ 即： $$ \begin{align} &k[i]=0,b[i]=0&i\in S\\ &k[i]=\frac1{d-\sum_{j\in ch[i]}k_j},b[i]=\frac{d+\sum_{j\in ch[i]}b_j}{d-\sum_{j\in ch[i]}k_j}&i\notin S\\ &k[i]=0,b[i]=\frac{d+\sum_{j\in ch[i]}b_j}{d-\sum_{j\in ch[i]}k_j}&i=x \end{align} $$ 最后做一个 $FMT$ 统计答案即可。

提前预处理答案复杂度就是 $O(n\times 2^n+Q)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,q,x;

#define MAXN 19

int f[1 << 18];

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int deg[MAXN];

void add(int a,int b)

{

	++deg[a];++deg[b];

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

bool tag[MAXN];

#define MOD 998244353

int power(int a,int b)

{

	int res = 1;

	for(;b > 0;b = b >> 1,a = 1ll * a * a % MOD)if(b & 1)res = 1ll * res * a % MOD;

	return res;

}

struct state

{

	int k,b;

};

state dp(int k,int fa)

{

	if(tag[k])return (state){0,0};

	int sumk = 0,sumb = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to == fa)continue;

		state nxt = dp(e[i].to,k);

		sumk = (sumk + nxt.k) % MOD;sumb = (sumb + nxt.b) % MOD;

	}

	int K = power((deg[k] - sumk + MOD) % MOD,MOD - 2);

	if(k == x)K = 0;

	int B = 1ll * (deg[k] + sumb) * power((deg[k] - sumk + MOD) % MOD,MOD - 2) % MOD;

	return (state){K,B};

}

int cnt[1 << 18];

int g[1 << 18];

int main()

{

	scanf("%d%d%d",&n,&q,&x);

	for(int i = 1;i < n;++i)add(rd(),rd());

	for(int s = 0;s < (1 << n);++s)

	{

		memset(tag,false,sizeof(tag));

		for(int i = 1;i <= n;++i)if((s >> (i - 1)) & 1)tag[i] = true;

		f[s] = dp(x,0).b;

		cnt[s] = cnt[s >> 1] + (s & 1);

	}

	for(int s = 0;s < (1 << n);++s)

	{

		if(cnt[s] & 1)g[s] = f[s];

		else g[s] = (MOD - f[s]) % MOD;

	}

	for(int i = 0;i < n;++i)

		for(int j = 0;j < (1 << n);++j)

			if(j & (1 << i))g[j] = (g[j] + g[j ^ (1 << i)]) % MOD;

	int k,v;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d",&k);

		int s = 0;

		for(int j = 1;j <= k;++j)

		{

			scanf("%d",&v);

			s ^= (1 << (v - 1));

		}

		printf("%d\n",g[s]);

	}

	return 0;

}