如果直接dp，狀態里肯定要帶上已走過的點的集合，感覺上不太好做。
考慮一種對期望的minmax容斥：
其中Max(S)為遍歷完S集合的期望步數，Min(S)為遍歷到S集合中一個點的期望步數。當然才不管怎么證，反正看上去非常優美。
條件概率邊緣概率聯合概率， 設f[i][S]為由i節點出發的Min(S)，顯然有f[i][S]=Σf[j][S]/di+1。暴力高斯消元復雜度就炸掉了。
注意到給出的是一棵樹，現在連這個性質都沒用到當然沒法做。根據一個我沒見過的套路，可以考慮把f[i]表示成a·f[fa]+b的形式，大力推一波式子就可以了。
求出f后，暴力枚舉子集容斥進行預處理是O(3n)的，類似高維前綴和直接遞推就是O(2nn)。然后就可以O(1)回答每個詢問了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 18 #define P 998244353 char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,m,S,p[N],f[N][1<<N],size[1<<N],d[N],a[N],b[N],t; struct data{int to,nxt; }edge[N<<1]; void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} int ksm(int a,int k) {int s=1;for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P;return s; } int inv(int a){return ksm(a,P-2);} void dfs(int k,int from,int S) {for (int i=p[k];i;i=edge[i].nxt)if (edge[i].to!=from) dfs(edge[i].to,k,S);if (S&(1<<k)) a[k]=b[k]=0;else{int A=0,B=0;for (int i=p[k];i;i=edge[i].nxt)if (edge[i].to!=from) A=(A+a[edge[i].to])%P,B=(B+b[edge[i].to])%P;a[k]=inv((d[k]-A+P)%P),b[k]=1ll*(B+d[k])*a[k]%P;} } void dfs2(int k,int from,int S) {for (int i=p[k];i;i=edge[i].nxt)if (edge[i].to!=from){f[edge[i].to][S]=(1ll*a[edge[i].to]*f[k][S]+b[edge[i].to])%P;dfs2(edge[i].to,k,S);} } int main() { #ifndef ONLINE_JUDGEfreopen("loj2542.in","r",stdin);freopen("loj2542.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read(),m=read(),S=read()-1;for (int i=1;i<n;i++){int x=read()-1,y=read()-1;addedge(x,y),addedge(y,x);d[x]++,d[y]++;}for (int i=1;i<(1<<n);i++)for (int j=0;j<n;j++)if (i&(1<<j)) {dfs(j,j,i);dfs2(j,j,i);break;}for (int i=1;i<(1<<n);i++){size[i]=size[i^(i&-i)]+1;if (!(size[i]&1)) f[S][i]=(P-f[S][i])%P;}for (int i=0;i<n;i++)for (int j=1;j<(1<<n);j++)if (j&(1<<i)) f[S][j]=(f[S][j]+f[S][j^(1<<i)])%P;/*for (int i=(1<<n)-1;i;i--)for (int j=i^(i&-i);j;j=j-1&i)f[S][i]=(f[S][i]+f[S][j])%P;*/while (m--){int k=read(),x=0;for (int i=1;i<=k;i++) x|=1<<read()-1;printf("%d\n",f[S][x]);}return 0; }
將編號分別為1~n的n個球隨機放入、?
