题目描述
给定一棵 n 个结点的树，你从点 x 出发，每次等概率随机选择一条与所在点相邻的边走过去。
有 Q 次询问，每次询问给定一个集合 S，求如果从 x 出发一直随机游走，直到点集 S 中所有点都至少经过一次的话，期望游走几步。
特别地，点 x（即起点）视为一开始就被经过了一次。
答案对 998244353 取模。
输入格式
第一行三个正整数 n,Q,x。
接下来 n-1 行，每行两个正整数 (u,v) 描述一条树边。
接下来 Q 行，每行第一个数 k 表示集合大小，接下来 k 个互不相同的数表示集合 S。
输出格式
输出 Q 行，每行一个非负整数表示答案。
样例输入
3 5 1
1 2
2 3
1 1
1 3
2 2 3
3 1 2 3
2 1 2
样例输出
0
4
4
4
1
Solution
考虑(min-max)容斥，即：
在这题，(min{S})表示第一次到达(S)集合的任何一个点的期望时间，(max{S})同理。
那么我们考虑如何求出(min{S})。
我们(O(2^n))的枚举每一个集合，那么我们考虑如何算。
设(f(x))表示从(x)点出发，第一次到达(S)的期望时间。
那么我们可以得到一个很显然的式子：
那么我们得到了一个(O(2^nn^3))的预处理，显然这是不允许的，我们需要优化。
这里有一个树上期望(dp)的套路：(f(x))一定和(f(fa))线性相关，那么我们可以写成(f(x)=A_xf(fa)+B_x)。
那么我们可以化一下上面那个式子：
移项可得：
对比一下可以得到：
那么直接(dfs)一遍就可以求出所有的(A,B)，注意到(dfs)到集合中的点就把(A,B)设成(0)然后(return)就好了。
那么我们可以在(O(2^nn))的时间内预处理出(min)。
但是如果这样写还是不能过，因为询问的复杂度上限是(O(Q2^n))。不过据说数据水这样能轻松过？
注意到(min-max)容斥那个容斥系数只和(T)相关，那么我们可以求出(min)之后先乘上一个系数，然后(fwt)一下求出子集和，就可以直接(O(2^n n))的预处理出(max)了。
那么对于询问就直接(O(1))输出就好了。
总复杂度(O((2^n+Q)n))。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 19;
const int maxm = (1<<18)+100;
const int mod = 998244353;
int head[maxn],tot,n,rt,Q,mn[maxm],f[maxn],A[maxn],B[maxn],d[maxn];
struct edge{int to,nxt;}e[maxn<<1];
int qpow(int a,int x) {
int res=1;
for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
return res;
}
void ins(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot,d[v]++;}
struct data{int a,b;};
data dfs(int x,int fa,int s) {
if(s>>(x-1)&1) return (data){0,0};
int a=0,b=0;data res;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].to!=fa) res=dfs(e[i].to,x,s),a=(a+res.a)%mod,b=(b+res.b)%mod;
res.a=qpow((d[x]-a)%mod,mod-2);
res.b=1ll*res.a*(b+d[x])%mod;
return res;
}
void fwt(int *r,int m) {
for(int i=1;i<m;i<<=1)
for(int j=0;j<m;j+=i<<1)
for(int k=0;k<i;k++)
r[i+j+k]=(r[i+j+k]+r[j+k])%mod;
}
int k,a[maxn];
int main() {
read(n),read(Q),read(rt);
for(int i=1,x,y;i<n;i++) read(x),read(y),ins(x,y),ins(y,x);
for(int i=1;i<(1<<n);i++) {
mn[i]=dfs(rt,0,i).b;
mn[i]=mn[i]*(__builtin_popcount(i)&1?1:-1);
}
fwt(mn,1<<n);
while(Q--) {
read(k);int res=0;
for(int i=1,x;i<=k;i++) read(x),res|=1<<(x-1);
write((mn[res]+mod)%mod);
}
return 0;
}