[PKUWC2018]随机游走

容斥 DP 期望

---

题面

给定一棵$n$个结点的树，你从点$x$出发，每次等概率随机选择一条与所在点相邻的边走过去。
有$Q$次询问，每次询问给定一个集合$S$，求如果从$x$出发一直随机游走，直到点集$S$中所有点都至少经过一次的话，期望游走几步。
特别地，点$x$（即起点）视为一开始就被经过了一次。

• $n\leq18,Q\leq5000$

解析

咦？$n\leq18$？我会状压！
咦？所有点都至少经过一次？求期望？我会$Min-Max$容斥！
以上为看题想法

还记得[HNOI2013]游走吧？
在那一道题中，由于转移具有后效性，我们只能用解方程来求出到每个点的概率。

但这里是一颗树！转移没有后效性。
于是可以像$dp$一般转移结果。
设$f[i]$表示到达第一次到达$i$号点的期望次数。
先列一个基本的期望转移式：($d[u]$表示$u$号点的度数，$v$为$u$点的儿子）

$$f[u]=\frac{1}{d[u]}(f[fa]+1+\sum_{v\in son}(f[v]+1))$$
$$f[u]=\frac{1}{d[u]}f[fa]+\frac{1}{d[u]}\sum_{v\in son}f[v]+1$$
根据套路，树上期望问题中，到点$u$的期望次数可以表示为$f[u]=A*f[fa]+B$。
依此继续化式子：
$$f[u]=\frac{1}{d[u]}f[fa]+\frac{1}{d[u]}\sum_{v\in son}(A[v]*f[u]+B[v])+1$$
$$(1-\frac{A[v]}{d[u]})f[u]=\frac{1}{d[u]}f[fa]+\frac{1}{d[u]}\sum_{v\in son}B[v]+1$$
$$(d[u]-A[v])f[u]=f[fa]+\sum_{v\in son}B[v]+d[u]$$
$$f[u]=\frac{1}{d[u]-A[v]}f[fa]+\frac{\sum_{v\in son}B[v]+d[u]}{d[u]-A[v]}$$
则 $$A=\frac{1}{d[u]-A[v]}$$ $$B=\frac{\sum_{v\in son}B[v]+d[u]}{d[u]-A[v]}$$

枚举所有$S$，按上述式子转移。一旦遇到集合内的数，$A[u]=B[u]=0$并$return$。
这样就可得到所有的$E(min(S))$（在出发点）。

然后$Min-Max$容斥就只要用个结论：

$$E(\max(S))=\sum_{S'\in S}E(\min(S'))*(-1)^{|S'|+1}$$
复杂度$O(2^nn)$。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int mod=998244353,N=20;
struct Edge{int to,nxt;}e[N<<1];
int n,Q,rt,h[N],cnt,a[N],k,mx,q[N],d[N];
ll A[N],B[N],ans,res[(int)(2e6+100)];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u]};h[u]=cnt;++d[u];}
il ll gi()
{
   re ll x=0,t=1;
   re char ch=getchar();
   while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
   if(ch=='-') t=-1,ch=getchar();
   while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
   return x*t;
}
il ll ksm(re ll S,re ll o)
{
  re ll T=S;S=1;
  while(o)
    {
      if(o&1) S=S*T%mod;
      T=T*T%mod;
      o>>=1;
    }
  return S;
}
il void dfs(re int u,re int fa,re int S)
{
  if((1<<u-1)&S) {A[u]=B[u]=0;return;}
  re ll a=0,b=0;
  for(re int i=h[u];i+1;i=e[i].nxt)
    {
      re int v=e[i].to;
      if(v==fa) continue;
      dfs(v,u,S);
      (a+=A[v])%=mod;(b+=B[v])%=mod;
    }
  re ll ysn=ksm((d[u]-a+mod)%mod,mod-2);
  A[u]=ysn;
  B[u]=(d[u]+b)*ysn%mod;
}
il void Min_Max(re int x,re int sz,re int S)
{
  if(x>k)
    {
      if(sz&1) (ans+=res[S])%=mod;
      else ans=(ans+mod-res[S])%mod;
      return;
    }
  Min_Max(x+1,sz,S);
  Min_Max(x+1,sz+1,S|(1<<q[x]-1));
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();Q=gi();rt=gi();mx=(1<<n)-1;
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi();
      add(u,v);add(v,u);
    }
  fp(S,1,mx)
    {
      fp(i,1,n) A[i]=B[i]=0;
      dfs(rt,0,S);
      res[S]=B[rt];
    }
  while(Q--)
    {
      k=gi();ans=0;
      fp(i,1,k) q[i]=gi();
      Min_Max(1,0,0);
      printf("%lld\n",ans);
    }
  return 0;
}