题意

题目链接

Sol

考虑直接对询问的集合做MinMax容斥

设\(f[i][sta]\)表示从\(i\)到集合\(sta\)中任意一点的最小期望步数

按照树上高斯消元的套路，我们可以把转移写成\(f[x] = a_x f[fa] + b_x\)的形式

然后直接推就可以了

更详细的题解

#include<bits/stdc++.h>

#define LL long long

using namespace std;

const int MAXN = 1e6 + 10, mod = 998244353;

inline int read() {

    char c = getchar(); int x = 0, f = 1;

    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

    return x * f;

}

int mul(int x, int y) {return 1ll * x * y % mod;}

int add(int x, int y) {if(x + y < 0) return x + y + mod; else return x + y >= mod ? x + y - mod : x + y;}

int fp(int a, int p) {

    int base = 1;

    for(; p; p >>= 1, a = mul(a, a))

        if(p & 1) base = mul(base, a);

    return base;

}

int inv(int x) {

    x = (x + mod) % mod;

    return fp(x, mod - 2);

}

int N, Q, S, Lim, g[MAXN], deg[MAXN], a[MAXN], b[MAXN], siz[MAXN];

vector<int> v[MAXN];

void dfs(int x, int fa, int sta) {

    if(sta & (1 << x - 1)) {a[x] = b[x] = 0; return ;}

    int ta = 0, tb = 0;

    for(int i = 0; i < v[x].size(); i++) {

        int to = v[x][i]; if(to == fa) continue;

        dfs(to, x, sta);

        ta += a[to]; tb += b[to];

    }

    a[x] = inv(deg[x] - ta);

    b[x] = mul((tb + deg[x]), inv(deg[x] - ta));

}

int main() {

    N = read(); Q = read(); S = read(); Lim = (1 << N) - 1;

    for(int i = 1; i <= N - 1; i++) {

        int x = read(), y = read();

        v[x].push_back(y); v[y].push_back(x);

        deg[x]++; deg[y]++;

    }

    for(int sta = 1; sta <= Lim; sta++) {

        siz[sta] = siz[sta >> 1] + (sta & 1);

        dfs(S, 0, sta);

        g[sta] = b[S];

    }

    while(Q--) {

        int k = read(), S = 0, ans = 0;

        for(int i = 1; i <= k; i++) S |= (1 << (read() - 1));

        for(int i = S; i; i = (i - 1) & S) {

            if(siz[i] & 1) ans = add(ans, g[i]);

            else ans = add(ans, -g[i]);

        }

        printf("%d\n", ans);

    }

    return 0;

}