题目描述

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

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

特别地，点 $x$（即起点）视为一开始就被经过了一次。

答案对 $998244353$ 取模。

输入格式

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

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

接下来 $Q$ 行，每行第一个数 $k$ 表示集合大小，接下来 $k$ 个互不相同的数表示集合 $S$。

输出格式

输出 $Q$ 行，每行一个非负整数表示答案。

数据范围与提示

对于 $20\%$ 的数据，有 $1\le n,Q\le 5$。

另有 $10\%$ 的数据，满足给定的树是一条链。

另有 $10\%$ 的数据，满足对于所有询问有 $k=1$。

另有 $30\%$ 的数据，满足 $1\le n\le 10,Q=1$。

对于 $100\%$ 的数据，有 $1\le n\le 18$，$1\le Q\le 5000$，$1\le k\le 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 )$;
• 1 #include
          
            2 #define mod 998244353 3 using namespace std; 4 const int N=20,M=100010; 5 int n,q,s,S,num[1<<18],f[1<<18],o=1,hd[N],A[N],B[N],d[N],inv[M]; 6 struct Edge{
        int v,nt;}E[N<<1]; 7 void adde(int u,int v){ 8     E[o]=(Edge){v,hd[u]};hd[u]=o++; 9     E[o]=(Edge){u,hd[v]};hd[v]=o++; 10 }11 inline int Inv(int x){
        return x<1e5?inv[x]:1ll*(mod-mod/x)*Inv(mod%x)%mod;}12 void dfs(int u,int fa){13     if(S&1<<(u-1)){A[u]=B[u]=0;return;}14     int s1=0,s2=0;15     for(int i=hd[u];i;i=E[i].nt){16         int v=E[i].v;17         if(v==fa)continue;18         dfs(v,u);19         s1=(s1+A[v])%mod,s2=(s2+B[v])%mod;20     }21     A[u]=Inv((d[u]-s1+mod)%mod);22     B[u]=1ll*A[u]*(s2+d[u])%mod;23 }24 int main(){25     #ifndef ONLINE_JUDGE26     freopen("loj2542.in","r",stdin);27     freopen("loj2542.out","w",stdout);28     #endif29     scanf("%d%d%d",&n,&q,&s);30     inv[1]=1;31     for(int i=2;i<=1e5;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;32     for(int i=1,u,v;i
           
            >1]+(i&1);40         f[i]=(num[i]&1)?B[s]:(mod-B[s])%mod;41     }42     for(int i=0;i
            
             >i&1)f[j]=(f[j]+f[j^(1<