[LOJ2542][PKUWC2018]随机游走(MinMax容斥+树上高斯消元)

MinMax容斥将问题转化为求x到S中任意点的最小时间。

树形DP，直接求概率比较困难，考虑只求系数。最后由于x节点作为树根无父亲，所以求出的第二个系数就是答案。

https://blog.csdn.net/dearbaba_8520/article/details/80556499

$O((n+q)2^n)$

#include<cstdio>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
using namespace std;

const int N=20,mod=998244353;
int n,Q,rt,u,v,cnt,A[N],B[N],d[N],invd[N],h[N],to[N<<1],nxt[N<<1],Min[1<<N],bit[1<<N];
void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; }

int ksm(int a,int b){
    int res=1;
    for (; b; a=1ll*a*a%mod,b>>=1)
        if (b & 1) res=1ll*res*a%mod;
    return res;
}

void DP(int x,int fa,int S){
    if ((1<<(x-1))&S){ A[x]=B[x]=0; return; }
    int ta=0,tb=0;
    For(i,x) if ((k=to[i])!=fa)
        DP(k,x,S),ta=(ta+A[k])%mod,tb=(tb+B[k])%mod;
    int c=ksm((1-1ll*ta*invd[x]%mod+mod)%mod,mod-2);
    A[x]=1ll*invd[x]*c%mod; B[x]=(1+1ll*tb*invd[x])%mod*c%mod;
}

int main(){
    freopen("walk.in","r",stdin);
    freopen("walk.out","w",stdout);
    scanf("%d%d%d",&n,&Q,&rt);
    rep(i,2,n) scanf("%d%d",&u,&v),add(u,v),add(v,u),d[u]++,d[v]++;
    rep(i,1,n) invd[i]=ksm(d[i],mod-2);
    int ed=(1<<n)-1;
    rep(i,0,ed) DP(rt,0,i),Min[i]=B[rt],bit[i]=bit[i>>1]+(i&1);
    while (Q--){
        int S=0,ans=0,x,k; scanf("%d",&k);
        while (k--) scanf("%d",&x),S|=1<<(x-1);
        for (int i=S; i; i=(i-1)&S) ans=(ans+1ll*(bit[i]&1 ? 1 : -1)*Min[i]+mod)%mod;
        printf("%d
",ans);
    }
    return 0;
}