题目概述

有一棵树，刚开始你在 $X​$ ，每次随机走到相邻的点。有 $q​$ 个询问，每次询问给出一些点，求把这些点至少经过一次的期望时间。

解题报告

不难想到Min-Max容斥，令 $min(S)$ 表示第一次走到 $S$ 集合中的点的期望时间。然后我可能是智障，我刚开始认为 $min(S)=min\{f(i)|i\in S\}$ ，其中 $f(i)$ 表示 $X$ 第一次走到 $i$ 的期望时间（用高斯消元求解），这显然是错的，因为走到 $i$ 的途中可能就已经经过其他在 $S$ 中的点导致违法。

那么正确的定义应该加上一维：$f(i,S)$ 表示从 $i$ 出发第一次到达 $S$ 这个集合中的点的期望时间，则可以列出 $n$ 个方程来求解：

$$ f(i,S)=\begin{cases}{1\over d_i}\sum_{(i,j)\in E}f(j,S)+1&i\not\in S\\0&i\in S\end{cases} $$

这样是 $O(2^nn^3)$ 的，法老表示可以用奇技淫巧搞过去……我没有深入探究过……反正朴素消元是TLE的……

接下来上套路：在树上的高斯消元可以变成 $f(x)=a_xf(fa_x)+b_x$ 的形式，这是怎么想到的呢？考虑在树上的方程：

$$ f(x,S)=\begin{cases}{1\over d_x}(\sum f(son,S)+f(fa_x,S))+1&x\not\in S,\text{x is not leaf}\\{1\over d_x}f(fa_x,S)+1&x\not\in S,\text{x is leaf}\\0&x\in S\end{cases} $$

从叶子往上代入，移项之后发现每次就只剩了父亲节点，并没有儿子节点，于是可以写成 $f(x)=a_xf(fa_x)+b_x$ 。所以对于 $f(x,S)$ ：

$$ f(x,S)={1\over d_x}f(fa_x,S)+{1\over d_x}f(x,S)\sum a_{son}+{1\over d_x}\sum b_{son}+1\\ f(x,S)={1\over d_x(1-{1\over d_x}\sum a_{son})}f(fa_x,S)+{1\over d_x(1-{1\over d_x}\sum a_{son})}\sum b_{son}+{1\over1-{1\over d_x}\sum a_{son}} $$

由于 $f(X,S)$ 并没有父亲所以 $min(S)=f(X,S)=b_X$ ，就可以求出 $max(S)$ 了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;typedef long double DB;
const int maxn=18,maxs=1<<maxn,MOD=998244353;

int n,te,st,d[maxn+5],f[maxn+5],g[maxn+5],ans[maxs],cnt[maxs];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline int Inv(int x) {int INV=1;while (x>1) INV=(LL)INV*(MOD-MOD/x)%MOD,x=MOD%x;return INV;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void Solve(int s,int x,int pre=0,int A=0,int B=0){
    for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Solve(s,son[j],x),AMOD(A,g[son[j]]),AMOD(B,f[son[j]]);
    if (s>>x-1&1) f[x]=g[x]=0; else{
        int INV=Inv(d[x]);A=Inv((MOD+1-(LL)A*INV%MOD)%MOD);B=(LL)B*INV%MOD;AMOD(B,1);
        g[x]=(LL)INV*A%MOD;f[x]=(LL)B*A%MOD;
    }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&te,&st);
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x),d[x]++,d[y]++;
    for (int s=1;s<(1<<n);s++) Solve(s,st),cnt[s]=cnt[s>>1]+(s&1),ans[s]=(cnt[s]&1?f[st]:MOD-f[st])%MOD;
    for (int i=0;i<n;i++) for (int s=1<<i;s<(1<<n);s=(s+1)|(1<<i)) AMOD(ans[s],ans[s^(1<<i)]);
    while (te--){
        int K,s=0;scanf("%d",&K);for (int i=1,x;i<=K;i++) scanf("%d",&x),s|=1<<x-1;
        printf("%d\n",ans[s]);
    }return 0;
}