解：首先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飞.....
#include <bits/stdc++.h>
const int N = , MO = ;
inline void read(int &x) {
x = ;
char c = getchar();
while(c < '' || c > '') c = getchar();
while(c >= '' && c <= '') {
x = x * + c - ;
c = getchar();
}
return;
}
struct Edge {
int nex, v;
}edge[N << ]; int tp;
int n, rt, e[N], A[N], B[N], now, in[N], ans[ << ], cnt[ << ], ans2[ << ];
inline int qpow(int a, int b) {
int ans = ;
a = (a + MO) % MO;
while(b) {
if(b & ) ans = 1ll * ans * a % MO;
a = 1ll * a * a % MO;
b = b >> ;
}
return ans;
}
inline void add(int x, int y) {
tp++;
edge[tp].v = y;
edge[tp].nex = e[x];
e[x] = tp;
return;
}
void DFS(int x, int f) {
if((( << (x - )) | now) == now) {
A[x] = B[x] = ;
return;
}
int sa = , sb = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == f) continue;
DFS(y, x);
sa = (sa + A[y]) % MO;
sb = (sb + B[y]) % MO;
}
A[x] = qpow(in[x] - sa, MO - );
B[x] = 1ll * A[x] * (in[x] + sb) % MO;
return;
}
int main() {
int q;
read(n); read(q); read(rt);
for(register int i = , x, y; i < n; i++) {
read(x); read(y);
add(x, y); add(y, x);
in[x]++; in[y]++;
}
int lm = << n;
/*for(now = 1; now < lm; now++) {
//memset(A, )
DFS(rt, 0);
ans[now] = B[rt];
}*/
memset(ans, -, sizeof(ans));
memset(ans2, -, sizeof(ans2));
for(register int i = ; i < lm; i++) {
cnt[i] = + cnt[i - (i & (-i))];
}
/// prework OVER
for(register int i = , k; i <= q; i++) {
read(k);
int s = ;
for(register int j = , x; j <= k; j++) {
read(x);
s |= ( << (x - ));
}
int Ans = ;
if(ans2[s] != -) {
Ans = ans2[s];
}
else {
for(register int t = s; t; t = (t - ) & s) {
if(ans[t] == -) {
now = t;
DFS(rt, );
ans[t] = B[rt];
}
if(cnt[t] & ) Ans = (Ans + ans[t]) % MO;
else Ans = (Ans - ans[t] + MO) % MO;
}
ans2[s] = Ans;
}
printf("%d\n", (Ans + MO) % MO);
}
return ;
}
AC代码