题意分析
Min-max 容斥
记走到点 $i$ 的期望步数为 $t_i$，$S=\set{1,2,3,\cdots,n}$，题目所求即：
\[E\left(\max_{i\in S}t_i\right)\]根据 Min-max 容斥，等价于求：
\[\sum_{T\subseteq S}(-1)^{\vert T\vert-1}E\left(\min_{i\in T}t_i\right)\]树形 DP
注意到 $n\leq18$，因此枚举 $T$ 是可以被接受的，考虑如何对确定的 $T$ 计算 $E\left(\min\limits_{i\in T}t_i\right)$。
这其实就是从点 $x$ 开始，第一次走到 $T$ 中的任意一点的期望步数。
设从点 $i$ 开始，第一次走到 $T$ 中任意一点的期望步数为 $f_i$。若 $i\in T$，则 $f_i=0$。
将原图视为以 $x$ 为根节点的树，记 $\textit{son}_i$ 表示节点 $i$ 的子节点集，$\textit{deg}_i$ 表示节点 $i$ 的度数，$\textit{father}_i$ 表示节点 $i$ 的父节点。
则有：
\[f_u=\dfrac{1}{\textit{deg}_u}\left(f_{\textit{father}_u}+\sum_{v\in\textit{son}_u}f_v\right)+1\]但是，这并不好操作。因为可以用 $n$ 个点列出 $n$ 个方程后高斯消元，但是这样总时间复杂度就是 $\mathcal O(n^32^n)$，无法接受。
考虑利用树的性质（半线性结构，一个节点具有唯一的父节点）。
设 $f_u=k_u\cdot f_{\textit{father}_u}+b_u$，则有：
\[\begin{aligned} f_u&=\frac1{\textit{deg}_u}\left(f_{\textit{father}_u}+\sum_{v\in\textit{son}_u}(k_v\cdot f_u+b_v)\right)+1\\ \textit{deg}_uf_u&=f_{\textit{father}_u}+\sum_{v\in\textit{son}_u}(k_v\cdot f_u+b_v)+\textit{deg}_u\\ \textit{deg}_uf_u&=f_{\textit{father}_u}+\sum_{v\in\textit{son}_u}k_v\cdot f_u+\sum_{v\in\textit{son}_u}b_v+\textit{deg}_u\\ \left(\textit{deg}_u-\sum_{v\in\textit{son}_u}k_v\right)f_u&=f_{\textit{father}_u}+\sum_{v\in\textit{son}_u}b_v+\textit{deg}_u\\ f_u&=\dfrac{1}{\textit{deg}_u-\sum\limits_{v\in\textit{son}_u}k_v}f_{\textit{father}_u}+\dfrac{\sum\limits_{v\in\textit{son}_u}b_v+\textit{deg}_u}{\textit{deg}_u-\sum\limits_{v\in\textit{son}_u}k_v} \end{aligned}\]考虑到上面设的参数 $f_u=k_u\cdot f_{\textit{father}_u}+b_u$，则有：
\[\begin{cases} k_u&=\dfrac{1}{\textit{deg}_u-\sum\limits_{v\in\textit{son}_u}k_v}\\ b_u&=\dfrac{\sum\limits_{v\in\textit{son}_u}b_v+\textit{deg}_u}{\textit{deg}_u-\sum\limits_{v\in\textit{son}_u}k_v} \end{cases}\]因此，可以通过树形 DP 求出每一个点的 $k_i,v_i$。考虑到根节点 $x$ 没有父节点，在初始公式 \(f_u=\dfrac{1}{\textit{deg}_u}\left(f_{\textit{father}_u}+\sum\limits_{v\in\textit{son}_u}f_v\right)+1\) 中 $f_{\textit{father}_u}$ 就不应当出现，因此可视为 $0$，故：
\[f_x=b_x\]高维前缀和
枚举一次 $S$ 的子集是 $\mathcal O\left(2^n\right)$ 的，在 $Q\leq5000$ 次询问中重复做显然是不合理的，因为 Min-max 容斥中的 $E\left(\max\limits_{i\in S}t_i\right)$ 与 $S$ 无关。
因此可以考虑预处理出所有答案，直接用 $S$ 查询，那么便可以使用高维前缀和。
记 $\textit{ans}_T$ 表示 $T$ 的答案，那么记 $\textit{ans}’_T$ 表示 $T$ 及 $T$ 的所有子集的答案之和。
可以枚举 $i\in[1,n]$，若 $T$ 包含 $i$，那么就让 \(\textit{ans}'_T\) 加上 \(\textit{ans}'_{T\setminus\lbrace i\rbrace}\) 即可。其中，\(T\setminus\set{i}\) 表示 $T,\set{i}$ 的差集。
参考代码
1
2
3
4
5
6
7
for(int i=0;i<n;i++){
for(int T=0;T<=all;T++){
if(T&(1<<i)){
ans[T]=(1ll*ans[T]+ans[T^(1<<i)])%P;
}
}
}
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=18,P=998244353;
int qpow(int base,int n){
base%=P;
int ans=1;
while(n){
if(n&1){
ans=1ll*ans*base%P;
}
base=1ll*base*base%P;
n>>=1;
}
return ans;
}
int n,x;
int ans[1<<N|1];
vector<int>g[N+1];
int k[N+1],b[N+1];
int &root=x;
void dfs(int x,int fx,int T){
int ans=0;
int sumK=0,sumB=0;
for(int i:g[x]){
if(i==fx){
continue;
}
dfs(i,x,T);
sumK=(1ll*sumK+k[i])%P;
sumB=(1ll*sumB+b[i])%P;
}
if(T&(1<<x-1)){
k[x]=b[x]=0;
}else{
//一个坑：size()是无符号整数，注意类型转换。
k[x]=qpow((ll)g[x].size()-sumK,P-2);
b[x]=((ll)g[x].size()+sumB)%P*k[x]%P;
}
}
//统计集合大小
int popcount(int n){
int ans=0;
while(n){
ans++;
n-=n&-n;
}
return ans;
}
void pre(){
int all=(1<<n)-1;
for(int T=0;T<=all;T++){
dfs(x,0,T);
ans[T]=b[x];
if((popcount(T)+1)&1){
ans[T]=-ans[T];
}
}
for(int i=0;i<n;i++){
for(int T=0;T<=all;T++){
if(T&(1<<i)){
ans[T]=(1ll*ans[T]+ans[T^(1<<i)])%P;
}
}
}
}
int query(int S){
if(ans[S]<0){
ans[S]+=P;
}
return ans[S];
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int q;
cin>>n>>q>>x;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
pre();
while(q--){
int pl;
cin>>pl;
int S=0;
while(pl--){
int p;
cin>>p;
S|=1<<p-1;
}
cout<<query(S)<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
