其实不是很难啦

min-max容斥既视感

设f[x]表示从x走到S中第一个点的期望步数

f[x]=1/d[x]*(f[fa[x]])+∑1/d[x]*(f[ch[x]])+1

这个有环

利用f[x]=A*f[fa[x]]+B的套路代换

得到A，B的递推式

对于x=rt，f[fa[x]]=0,所以f[x]=Bx了

对于叶子，结果恰好也是A=1,B=1

 

可以2^n枚举S，再O(nlogn)log有逆元，得到答案

对于Q，直接2^n枚举子集

O((nlogn+Q)*2^n))

因为2^n跑不满，可以过。

 

或者，预处理答案，O(1)回答

O((nlogn)+3^n+Q))

 

代码（法一）：

#include
     
      #define il inline#define reg register int#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){    char ch;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}namespace Miracle{const int N=20;const int mod=998244353;int n,q;int rt;int qm(int x,int y){    int ret=1;    while(y){        if(y&1) ret=(ll)ret*x%mod;        x=(ll)x*x%mod;        y>>=1;    }    return ret;}int A[N],B[N];int ans[1<<18];int sz[1<<18];int S;int d[N];struct node{    int nxt,to;}e[2*N];int hd[N],cnt;void add(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}void dfs(int x,int fa){    //A[x]=0;B[x]=0;    if(S&(1<<(x-1))) {        A[x]=0,B[x]=0;        return;    }    int sb=0,sa=0;    int son=0;    for(reg i=hd[x];i;i=e[i].nxt){        int y=e[i].to;        if(y==fa) continue;        ++son;        dfs(y,x);        sb=(sb+B[y])%mod;        sa=(sa+A[y])%mod;    }        if(son){        A[x]=qm((d[x]-sa+mod)%mod,mod-2);        B[x]=((ll)sb+d[x])*qm((d[x]-sa+mod)%mod,mod-2)%mod;    }else{        A[x]=1;        B[x]=1;    }}int main(){    rd(n);rd(q);rd(rt);    int x,y;    for(reg i=1;i
      
       >1]+(S&1);        dfs(rt,0);        ans[S]=B[rt];    //    cout<<" S "<
       <<" : "<
        
         <<" A "<
         
          <