$ Min$-$Max$容斥真好用
$ PKUWC$滚粗后这题一直在$ todolist$里
今天才补掉..还要更加努力啊..
题意：给一棵不超过$ 18$个节点的树，$ 5000$次询问，每次问从根随机游走走遍一个集合的期望步数
$ Solution:$
考虑$ Min$-$Max$容斥
有$ Max(S)=\sum\limits_{T \subseteq S}(-1)^{|T|+1}Min(T)$
其中$ S,T$是一个集合，$Max(S)$表示$ S$中最大元素，$Min(S)$同理
$ update$评论区已经给出证明
我们设集合$ S$表示走到每个点的期望时间
显然走遍一个集合的期望时间就是$ Max(S)$
且第一次走到某集合的期望时间是$ Min(S)$
$ Max(S)$不容易计算，我们转而求解$ Min(S)$
令$f_i$表示从点$ i$随机游走第一次走到集合$ S$的期望步数
这个显然可以高斯消元，不过复杂度略大
由于转移是在树上，可以直接在树上$ O(n)$消元
我们令$ f_i=k_if_{fa[i]}+b_i$
当$ i$在集合$ S$中的时候$k_i=b_i=0$否则进行转移
转移的时候把当前点孩子的$ k$和$ b$算出然后代到当前点的方程中算出当前点的$ k$和$ b$
这样可以在$O(2^n·n*算逆元复杂度)$的时间复杂度内算出所有的$ Min(S)$
然后直接容斥算$ Max(S)$,复杂度是$ 5000*2^n$的
我们可以提前预处理每个$ Max(S)$每次枚举子集转移，时间复杂度是$ 3^n$的
据说都能过
不过其实这部分可以优化到$ 2^n*n$的
我们直接根据$ popcount(S)$的奇偶性来判断是否给$ Min(S)$乘上$ -1$
然后直接高维前缀和即可
$ my \ code:$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define p 998244353
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x = ; char zf = ; char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') zf = -, ch = getchar();
while (isdigit(ch)) x = x * + ch - '', ch = getchar(); return x * zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt,Root;
struct ret{
int k,b;//k*father + b
ret operator +(const ret s)const{
return {(k+s.k)%p,(b+s.b)%p};
}
ret operator *(const int s)const{
return {1ll*k*s%p,1ll*b*s%p};
}
}f[][<<];
int F[],L[],N[],a[],d[],inv[],Min[<<];
void add(int x,int y){
a[++k]=y;
if(!F[x])F[x]=k;
else N[L[x]]=k;
L[x]=k;
}
int ksm(int x,int y){
int ans=;
for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*x*ans%p;;
return (ans+p)%p;
}
ret dfs(int x,int pre,int s){
if(s>>x-&)return{,};
ret now={,};
for(rt i=F[x];i;i=N[i])if(a[i]!=pre)now=now+dfs(a[i],x,s)*inv[d[x]];
const int Inv=ksm(-now.k,p-);
return {1ll*Inv*inv[d[x]]%p,1ll*Inv*(now.b+)%p};
}
#define cnt(x) __builtin_popcount(x)
int main(){
n=read();int Q=read();Root=read();
inv[]=inv[]=;
for(rt i=;i<=;i++)inv[i]=1ll*inv[p%i]*(p-p/i)%p;
for(rt i=;i<n;i++){
x=read();y=read();
add(x,y);
add(y,x);
d[x]++;d[y]++;
}
for(rt i=;i<(<<n);i++){
ret ans=dfs(Root,Root,i);
Min[i]=ans.b*(cnt(i)&?:-);
}
for(rt i=;i<n;i++)
for(rt j=;j<<<n;j++)if(j>>i&)(Min[j]+=Min[j^(<<i)])%=p;
while(Q--){
x=read();int sum=;
for(rt i=;i<=x;i++)
sum|=(<<read()-);
writeln((Min[sum]+p)%p);
}
return ;
}