题解
虽然我知道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('
')
#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();
}
颓颓颓颓颓