题目描述
给定一棵 nn 个结点的树，你从点 xx 出发，每次等概率随机选择一条与所在点相邻的边走过去。
有 QQ 次询问，每次询问给定一个集合 SS，求如果从 xx 出发一直随机游走，直到点集 SS 中所有点都至少经过一次的话，期望游走几步。
特别地，点 xx（即起点）视为一开始就被经过了一次。
答案对 998244353998244353 取模。
输入格式
第一行三个正整数 n,Q,xn,Q,x。
接下来 n-1n−1 行，每行两个正整数 (u,v)(u,v) 描述一条树边。
接下来 QQ 行，每行第一个数 kk 表示集合大小，接下来 kk 个互不相同的数表示集合 SS。
输出格式
输出 QQ 行，每行一个非负整数表示答案。
数据范围与提示
对于 20\%20% 的数据，有 1\leq n,Q\leq 51≤n,Q≤5。
另有 10\%10% 的数据，满足给定的树是一条链。
另有 10\%10% 的数据，满足对于所有询问有 k=1k=1。
另有 30\%30% 的数据，满足 1\leq n\leq 10 ,Q=11≤n≤10,Q=1。
对于 100\%100% 的数据，有 1\leq n\leq 181≤n≤18，1\leq Q\leq 50001≤Q≤5000，1\leq k\leq n1≤k≤n。
-
题解：
- 单点询问可以用高斯消元；
- 这个做法直接扩展到集合的话可以求出到$S$中任意一个点的期望步数；
- 如果对于一种状态，记录$S$中每个点被走到的步数$t$；
- 那么$S$中每个点都走到就是$t$的最大值，而刚刚求出来的是$t$的最小值；
- 套用最值反演：$max{S} = \sum_{T \subseteq S ,T \neq \emptyset } (-1)^{|T|-1} min{T}$；
- 现在只需要快速求出到$S$中任意一个点的期望步数，设$f_{u}$为$u$到$S$的期望步数：
- 可以得到：
- $f_{u} = \frac{1}{d_{u}} \sum_{v} f_{v} + 1 $
- 这里$v$表示和$u$相邻的点；
- 由于是一颗树，单独考虑父亲；
- $f_{u} = \frac{1}{d_{u}} f_{fa} + \frac{1}{d_{u}} \sum_{v}f_{v} + 1$ ①
- 这里$v$表示$u$的儿子节点；
- 假设已经处理好了$u$的儿子，为了能够递推，将式子写成：
- $f_{u} = A_{u}f_{fa} + B_{u}$ ②
- 那么$A_{v}$和$B_{v}$是已经处理好的，对①中的$v$用②，再对比化简的①和②：
- $$f_{u} = \frac{1}{d_{u} - \sum_{v}A_{v} } f_{fa} + \frac{d_{u} + \sum_{v}B_{v} }{d_{u} - \sum_{v} A_{v}}$$
- 这样就可以$O(n)$递推$AB$
- 用$fmt$处理反演部分的话，复杂度就是：$O(n2^n \ + \ q )$;
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
const int N=,M=;
int n,q,s,S,num[<<],f[<<],o=,hd[N],A[N],B[N],d[N],inv[M];
struct Edge{int v,nt;}E[N<<];
void adde(int u,int v){
E[o]=(Edge){v,hd[u]};hd[u]=o++;
E[o]=(Edge){u,hd[v]};hd[v]=o++;
}
inline int Inv(int x){return x<1e5?inv[x]:1ll*(mod-mod/x)*Inv(mod%x)%mod;}
void dfs(int u,int fa){
if(S&<<(u-)){A[u]=B[u]=;return;}
int s1=,s2=;
for(int i=hd[u];i;i=E[i].nt){
int v=E[i].v;
if(v==fa)continue;
dfs(v,u);
s1=(s1+A[v])%mod,s2=(s2+B[v])%mod;
}
A[u]=Inv((d[u]-s1+mod)%mod);
B[u]=1ll*A[u]*(s2+d[u])%mod;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("loj2542.in","r",stdin);
freopen("loj2542.out","w",stdout);
#endif
scanf("%d%d%d",&n,&q,&s);
inv[]=;
for(int i=;i<=1e5;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=,u,v;i<n;++i){
scanf("%d%d",&u,&v);
adde(u,v);
d[u]++,d[v]++;
}
for(int i=;i<<<n;++i){
S=i;dfs(s,);
num[i]=num[i>>]+(i&);
f[i]=(num[i]&)?B[s]:(mod-B[s])%mod;
}
for(int i=;i<n;++i)
for(int j=<<i;j<<<n;++j){
if(j>>i&)f[j]=(f[j]+f[j^(<<i)])%mod;
}
for(int i=,k;i<=q;++i){
scanf("%d",&k);
S=;for(int j=,x;j<=k;++j)scanf("%d",&x),S^=<<(x-);
printf("%d\n",f[S]);
}
return ;
}