用到了概率期望的很多技巧。
首先要求的是走遍集合中所有节点步数的期望，也就是步数最大值的期望，根据 \(\text{min-max}\) 容斥，有：
\[E\left(\max_{i\in S} x_i\right)=\sum_{T\subseteq S,T\neq \varnothing} (-1)^{|T|-1} E\left(\min_{j\in T} x_j\right) \]如果我们可以求得最小值的期望，也就是首次到达一个被标记点的期望，就可以通过 \(O(n2^n)\) 的高维前缀和得到最大值的期望。
枚举集合 \(T\)，设 \(f_u\) 表示有根树上从 \(u\) 出发首次到达一个被标记点的期望步数。
容易得到式子：
\[\begin{cases} f_u=0&u\in T\\ f_u=\dfrac{\sum_{(u,v)\in E} f_v}{deg_u}+1&u\notin T \end{cases}\]高斯消元可以求解。
总复杂度 \(O(2^nn^3\log p+nQ)\)。
点击查看代码
inline int q_pow(int x,int p){
int res=1;
while(p){
if(p&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
p>>=1;
}
return res;
}
int n,q,rt;
vector<int> E[20];
int a[20][20];
inline void Gauss(){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j){
if(i==j) continue;
for(int k=i+1;k<=n+1;++k){
a[j][k]=(a[j][k]-1ll*a[i][k]*q_pow(a[i][i],mod-2)%mod*a[j][i]%mod+mod)%mod;
}
}
}
}
int Emin[(1<<20)+10],Emax[(1<<20)+10];
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
n=read(),q=read(),rt=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
E[u].push_back(v);
E[v].push_back(u);
}
for(int s=1;s<(1<<n);++s){
for(int i=1;i<=n;++i){
for(int j=1;j<=n+1;++j){
a[i][j]=0;
}
}
int cnt=0;
for(int i=1;i<=n;++i){
if(s&(1<<i-1)) a[i][i]=1,a[i][n+1]=0,++cnt;
else{
int now=(mod-q_pow(E[i].size(),mod-2));
a[i][i]=1,a[i][n+1]=1;
for(int j:E[i]) a[i][j]=now;
}
}
Gauss();
a[rt][n+1]=1ll*a[rt][n+1]*q_pow(a[rt][rt],mod-2)%mod;
if(cnt&1) Emin[s]=a[rt][n+1];
else Emin[s]=mod-a[rt][n+1];
Emax[s]=Emin[s];
}
for(int i=1;i<=n;++i){
for(int s=1;s<(1<<n);++s){
if(!(s&(1<<i-1))) Emax[s|(1<<i-1)]=(Emax[s|(1<<i-1)]+Emax[s])%mod;
}
}
while(q--){
int k=read(),s=0;
for(int i=1;i<=k;++i) s|=(1<<read()-1);
printf("%d\n",Emax[s]);
}
return 0;
}
由于矩阵中有意义的值只有 \(O(n)\) 个，高斯消元非常冗余，使用另一种消元方法——系数递推。
在树上表现为对于每个节点，用其父亲的答案去表示该节点的答案，即写成 \(f_u=a_u\times f_{fa}+b_u\) 的形式。
大力推一下：
\[\begin{aligned} f_u&=\dfrac{f_{fa}+\sum_{(u,v)\in E,v\neq fa} f_v}{deg_u}+1\\ deg_u\times f_u&=f_{fa}+\sum_{(u,v)\in E,v\neq fa} (a_v\times f_u+b_v)+deg_u\\ \left(deg_u-\sum_{(u,v)\in E,v\neq fa} a_v\right) f_u&=f_{fa}+deg_u+\sum_{(u,v)\in E,v\neq fa} b_v\\ f_u&=\dfrac{1}{deg_u-\sum_{(u,v)\in E,v\neq fa} a_v} \times f_{fa} + \dfrac{deg_u+\sum_{(u,v)\in E,v\neq fa} b_v}{deg_u-\sum_{(u,v)\in E,v\neq fa} a_v} \end{aligned}\]于是：
\[\begin{cases} a_u=\dfrac{1}{deg_u-\sum_{(u,v)\in E,v\neq fa} a_v}\\ b_u=\dfrac{deg_u+\sum_{(u,v)\in E,v\neq fa} b_v}{deg_u-\sum_{(u,v)\in E,v\neq fa} a_v} \end{cases}\]而最终的答案 \(f_{rt}=b_{rt}\)。
总复杂度：\(O(n2^n\log p+nQ)\)。
点击查看代码
inline int q_pow(int x,int p){
int res=1;
while(p){
if(p&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
p>>=1;
}
return res;
}
int n,q,rt;
vector<int> E[20];
int a[20],b[20];
int Emin[(1<<20)+10],Emax[(1<<20)+10];
void dfs(int u,int fa,int s){
int suma=0,sumb=0;
if(s&(1<<(u-1))) return;
for(int v:E[u]){
if(v==fa) continue;
dfs(v,u,s);
suma=(suma+a[v])%mod,sumb=(sumb+b[v])%mod;
}
// printf("u:%d suma:%d sumb:%d deg:%d\n",u,suma,sumb,(int)E[u].size());
a[u]=q_pow((E[u].size()-suma+mod)%mod,mod-2),b[u]=1ll*(E[u].size()+sumb)%mod*a[u]%mod;
}
int main(){
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
n=read(),q=read(),rt=read();
for(int i=1;i<n;++i){
int u=read(),v=read();
E[u].push_back(v);
E[v].push_back(u);
}
for(int s=1;s<(1<<n);++s){
// printf("*%d*\n",s);
int cnt=0;
for(int i=1;i<=n;++i){
a[i]=b[i]=0;
if(s&(1<<i-1)) ++cnt;
}
dfs(rt,0,s);
if(cnt&1) Emin[s]=b[rt];
else Emin[s]=mod-b[rt];
Emax[s]=Emin[s];
// printf("ans:%d\n",b[rt]);
}
for(int i=1;i<=n;++i){
for(int s=1;s<(1<<n);++s){
if(!(s&(1<<i-1))) Emax[s|(1<<i-1)]=(Emax[s|(1<<i-1)]+Emax[s])%mod;
}
}
while(q--){
int k=read(),s=0;
for(int i=1;i<=k;++i) s|=(1<<read()-1);
printf("%d\n",Emax[s]);
}
return 0;
}