解：首先minmax容斥变成经过集合t的第一个点就停止的期望步数。对于某个t，设从x开始的期望步数为f(x)
如果x∈t，f(x) = 0。否则f(x) = ∑f(y) / in[x] + 1
树上高斯消元。从叶子往上，可以发现每个点都可以表示为Af(fa) + B
于是我们推一波式子，，就可以对每个t，O(n)求出f(root)。
然后每个询问就枚举子集。
注意DFS的时候可以剪枝，遇到x∈t就返回，否则T飞.....
1 #include2 3 const int N = 30, MO = 998244353; 4 5 inline void read(int &x) { 6 x = 0; 7 char c = getchar(); 8 while(c < '0' || c > '9') c = getchar(); 9 while(c >= '0' && c <= '9') { 10 x = x * 10 + c - 48; 11 c = getchar(); 12 } 13 return; 14 } 15 16 struct Edge { 17 int nex, v; 18 }edge[N << 1]; int tp; 19 20 int n, rt, e[N], A[N], B[N], now, in[N], ans[1 << 19], cnt[1 << 19], ans2[1 << 19]; 21 22 inline int qpow(int a, int b) { 23 int ans = 1; 24 a = (a + MO) % MO; 25 while(b) { 26 if(b & 1) ans = 1ll * ans * a % MO; 27 a = 1ll * a * a % MO; 28 b = b >> 1; 29 } 30 return ans; 31 } 32 33 inline void add(int x, int y) { 34 tp++; 35 edge[tp].v = y; 36 edge[tp].nex = e[x]; 37 e[x] = tp; 38 return; 39 } 40 41 void DFS(int x, int f) { 42 if(((1 << (x - 1)) | now) == now) { 43 A[x] = B[x] = 0; 44 return; 45 } 46 int sa = 0, sb = 0; 47 for(int i = e[x]; i; i = edge[i].nex) { 48 int y = edge[i].v; 49 if(y == f) continue; 50 DFS(y, x); 51 sa = (sa + A[y]) % MO; 52 sb = (sb + B[y]) % MO; 53 } 54 55 A[x] = qpow(in[x] - sa, MO - 2); 56 B[x] = 1ll * A[x] * (in[x] + sb) % MO; 57 58 return; 59 } 60 61 int main() { 62 int q; 63 read(n); read(q); read(rt); 64 for(register int i = 1, x, y; i < n; i++) { 65 read(x); read(y); 66 add(x, y); add(y, x); 67 in[x]++; in[y]++; 68 } 69 70 int lm = 1 << n; 71 /*for(now = 1; now < lm; now++) { 72 //memset(A, ) 73 DFS(rt, 0); 74 ans[now] = B[rt]; 75 }*/ 76 memset(ans, -1, sizeof(ans)); 77 memset(ans2, -1, sizeof(ans2)); 78 79 for(register int i = 1; i < lm; i++) { 80 cnt[i] = 1 + cnt[i - (i & (-i))]; 81 } 82 83 /// prework OVER 84 for(register int i = 1, k; i <= q; i++) { 85 read(k); 86 int s = 0; 87 for(register int j = 1, x; j <= k; j++) { 88 read(x); 89 s |= (1 << (x - 1)); 90 } 91 int Ans = 0; 92 if(ans2[s] != -1) { 93 Ans = ans2[s]; 94 } 95 else { 96 for(register int t = s; t; t = (t - 1) & s) { 97 if(ans[t] == -1) { 98 now = t; 99 DFS(rt, 0);100 ans[t] = B[rt];101 }102 if(cnt[t] & 1) Ans = (Ans + ans[t]) % MO;103 else Ans = (Ans - ans[t] + MO) % MO;104 }105 ans2[s] = Ans;106 }107 printf("%d\n", (Ans + MO) % MO);108 }109 110 return 0;111 }