【题解】「PKUWC2018」随机游走 Min-Max 容斥+线性高斯消元 —Qiuly

设 $x$ 为树的根，对于每次讯问中 $S$ 中的任意一点 $a$ ，设 $t_a$ 表示 $x$ 到 $a$ 的步数，于是我们的答案就是 $E(\max(S))$ ，好像不是很好求，考虑求 $\min(S)$ 然后进行 $\rm{Min-Max}$ 容斥。

设 $f(u)$ 表示从点 $u$ 出发到达 $S$ 中的点的期望步数。设 $d_u$ 表示 $u$ 的度数，于是我们可以得到转移式：
$$
f(u)=\frac{f(fa_u)+1+\sum_{v\in son_u}(f(v)+1)}{d_u}\\
f(u)=1+\frac{f(fa_u)+\sum_{v\in son_u}f(v)}{d_u}\\
f(u)=\frac{1}{d_u}f(fa_u)+\frac{1}{d_u}\sum_{v\in son_u}f(v)+1\\
$$
考虑用线性高斯消元解决，设一个 $A_u,B_u$ ，令 $f(u)=A_uf(fa_u)+B_u$ ：
$$
f(u)=\frac{1}{d_u}f(fa_u)+\frac{1}{d_u}\sum_{v\in son_u}(A_vf(u)+B_v)+1\\
f(u)=\frac{1}{d_u}f(fa_u)+\sum_{v\in son_u}\frac{B_v}{d_u}+f(u)\sum_{v\in son_u}\frac{A_v}{d_u}+1\\
(1-\sum_{v\in son_u}\frac{A_v}{d_u})f(u)=\frac{1}{d_u}f(fa_u)+\sum_{v\in son_u}\frac{B_v}{d_u}+1\\
f(u)=\frac{\frac{1}{d_u}f(fa_u)}{1-\sum_{v\in son_u}\frac{A_v}{d_u}}+\frac{\sum_{v\in son_u}\frac{B_v}{d_u}+1}{1-\sum_{v\in son_u}\frac{A_v}{d_u}}\\
f(u)=f(fa_u)\frac{\frac{1}{d_u}}{1-\sum_{v\in son_u}\frac{A_v}{d_u}}+\frac{\sum_{v\in son_u}\frac{B_v}{d_u}+1}{1-\sum_{v\in son_u}\frac{A_v}{d_u}}\\
f(u)=f(fa_u)\frac{1}{d_u-\sum_{v\in son_u}A_v}+\frac{d_u+\sum_{v\in son_u}B_v}{d_u-\sum_{v\in son_u}A_v}\\
$$
于是我们得到了 $A_u,B_u$ 的递推式：
$$
\begin{cases}
A_u=\frac{1}{d_u-\sum_{v\in son_u}A_v}\\
B_u=\frac{d_u+\sum_{v\in son_u}B_v}{d_u-\sum_{v\in son_u}A_v}\\
\end{cases}
$$
补充一下，对于 $u\in S$ ，$f(u)=0$ .

然后对于每一个集合 $S$ ，都 $dfs$ 整棵树计算出 $f(x)$ ，然后每个询问直接 $\rm{Min-Max}$ 即可。

这题式子还挺好推的，最后我们就求出来了，$E(\min(S))=f_{x,S}$ ，其中 $f_{x,S}$ 表示当前枚举的集合为 $S$ 时对于 $f_x$ 的答案，显然这里 $f_x=B_x$ ，毕竟 $x$ 没有 $fa$ 。

Code：

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=20;
const ll mod=998244353;

int n,q,x,d[N],fa[N],siz[1<<N],head[N],cnt;
ll A[N],B[N],invd[N],res[1<<N];

struct Edge {int nxt,to;} G[N<<1];
inline void add(int u,int v) {
    G[++cnt]=(Edge){head[u],v},head[u]=cnt;
    G[++cnt]=(Edge){head[v],u},head[v]=cnt;
}   

inline ll pow(ll x,ll y,ll res=1) {
    x=(x%mod+mod)%mod;
    for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;
    return res;
}

template <typename _Tp> inline void IN(_Tp&x) {
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    if(flag) x=-x;
}

void dfs(int u,int f,int S) {
    if((1<<(u-1))&S) {A[u]=B[u]=0;return;}
    ll cnt1=0,cnt2=0;
    fa[u]=f;
    for(int i=head[u],v;i;i=G[i].nxt)
        if((v=G[i].to)!=f) dfs(v,u,S),cnt1+=A[v],cnt2+=B[v];
    cnt1%=mod,cnt2%=mod;
    ll res=pow(mod+1-invd[u]*cnt1,mod-2);
    A[u]=invd[u]*res%mod;
    B[u]=(1+invd[u]*cnt2%mod)*res%mod;
}

int main() {
    IN(n),IN(q),IN(x);
    for(int i=1,u,v;i<n;++i) 
        IN(u),IN(v),add(u,v),++d[u],++d[v];
    for(int i=1;i<=n;++i) invd[i]=pow(d[i],mod-2);
    for(int i=0;i<1<<n;++i) 
        siz[i]=siz[i>>1]+(i&1),dfs(x,0,i),res[i]=B[x];
    while(q--) {
        int k,S=0;IN(k);
        for(int i=1,x;i<=k;++i) IN(x),S|=(1<<(x-1));
        ll ans=0;
        for(int i=S;i;i=(i-1)&S)
            ans+=(siz[i]&1?1:-1)*res[i];
        ans=(ans%mod+mod)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}