题解

虽然我知道minmax容斥，但是……神仙能想到把这个dp转化成一个一次函数啊= =

我们相当于求给定的\(S\)集合里最后一个被访问到的点的时间，对于这样的max的问题，我们可以用容斥把它转化成min问题

也就是

\(max{S} = \sum_{T \subset S} (-1)^{|T| + 1}min{T}\)

然后我们变成要求对给定的集合，最早访问到其中的点的期望

设当前的点集为\(S\),\(f(u)\)为从u点出发最早到\(S\)中的点期望的步数

如果\(u \in S\)

\(f(u) = 0\)

否则

\(f(u) = \frac{1}{d[u]}(f(fa[u]) + 1)+ \frac{1}{d[u]}\sum (f(ch[u]) + 1)\)

我们发现，从叶子节点开始倒推，我们每个点都可以表示成

\(f(u) = A_u f(fa[u]) + B_u\)的式子

那么我们把这个式子代进去

设\(v\)代表\(u\)的儿子

\((1 - \frac{\sum A_{v}}{d[u]})f(u) = \frac{1}{d[u]}f(fa[u]) + (1 + \frac{\sum B_{v}}{d[u]})\)

从叶子开始倒退即可，我们把起点当根，那么答案就是起点的\(B_x\)

最后用FMT累加起来可以做到\(O(1)\)回答询问（也可以子集枚举累加）

复杂度\(O(n 2^n + Q)\)

代码

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

#include <cmath>

#include <bitset>

#define enter putchar('\n')

#define space putchar(' ')

//#define ivorysi

#define pb push_back

#define MAXN 100005

#define mo 974711

#define pii pair<int,int>

#define mp make_pair

#define fi first

#define se second

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;char c = getchar();T f = 1;

    while(c < '0' || c > '9') {

	if(c == '-') f = -1;

	c = getchar();

    }

    while(c >= '0' && c <= '9') {

	res = res * 10 - '0' + c;

	c = getchar();

    }

    res = res * f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) out(x / 10);

    putchar('0' + x % 10);

}

const int MOD = 998244353;

int N,Q,st,A[25],B[25],D[25],cnt,f[(1 << 18) + 5],inv[20];

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

int fpow(int x,int c) {

    int t = x,res = 1;

    while(c) {

	if(c & 1) res = mul(res,t);

	t = mul(t,t);

	c >>= 1;

    }

    return res;

}

struct node {

    int to,next;

}E[105];

int head[20],sumE;

void add(int u,int v) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    head[u] = sumE;

}

void dp(int u,int fa,int S) {

    if(S >> (u - 1) & 1) {++cnt;}

    A[u] = B[u] = 0;

    int SumA = 0,SumB = 0;

    for(int i = head[u] ; i ; i = E[i].next) {

	int v = E[i].to;

	if(v != fa) {

	    dp(v,u,S);

	    SumA = inc(SumA,A[v]);

	    SumB = inc(SumB,B[v]);

	}

    }

    if(S >> (u - 1) & 1) return;

    int m = inc(1,MOD - mul(SumA,inv[D[u]]));

    m = fpow(m,MOD - 2);

    int k = inc(1,mul(SumB,inv[D[u]]));

    A[u] = mul(inv[D[u]],m);

    B[u] = mul(k,m);

}

void Solve() {

    read(N);read(Q);read(st);

    int u,v;

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

	read(u);read(v);

	add(u,v);add(v,u);

	++D[u];++D[v];

    }

    inv[1] = 1;

    for(int i = 2 ; i <= N ; ++i) {

	inv[i] = mul(inv[MOD % i],(MOD - MOD / i));

    }

    for(int S = 1 ; S < (1 << N) ; ++S) {

	cnt = 0;

	dp(st,0,S);

	if((cnt + 1) & 1) f[S] = MOD - B[st];

	else f[S] = B[st];

	out(f[S]);space;

    }

    enter;

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

	for(int j = 1 ; j < (1 << N) ; ++j) {

	    if(j & i) f[j] = inc(f[j],f[j ^ i]);

	}

    }

    int k,S;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

颓颓颓颓颓