显然你如果直接带一个子集到树上dp的话复杂度是会炸上天的23333.
考虑期望也是可以进行min_max容斥的，也就是: max{S} = ∑ min{T} * (-1) ^( |T|+1 ) ，其中T是S的一个非空子集，max{S}和min{S}分别代表集合中所有条件都被满足的期望时间 和 集合中至少有一个条件被满足的期望时间， 当然对本题来说就是 所有钦定的点都被到过一次的期望时间 和 第一次到某个钦定的点的期望时间。。。。
发现min非常的好算，对于每个集合直接一次树上dp O(n * log 998244351) 就可以算出来了(千万不要用高斯消元。。。这种树上路径期望问题可以把每个节点的dp值表示 a * f(fa) + b的形式，dfs的时候直接算就行了)
然后把每个集合的min{}算出来之后就可以用类FMT的逆推方法推出每个集合的答案。
不过两者之间不同的是，FMT的式子是: f ‘(S‘) = ∑ f(S) * (-1) ^ ( |S‘| - |S|) ，而这个的是 f ‘(S‘) = ∑ f(S) * (-1) ^ ( |S|+1 )。
但其实并没有什么难度，因为我们把 S‘ 中1的个数按奇偶性讨论一下就可以直接在FMT之后的数组上修改成我们要的样子了。。。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define pb push_back
const int ha=998244353,N=300005;
inline int read(){
int x=0; char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘;
return x-1;
}
inline int add(int x,int y){ x+=y; return x>=ha?x-ha:x;}
inline void ADD(int &x,int y){ x+=y; if(x>=ha) x-=ha;}
int ksm(int x,int y){
int an=1;
for(;y;y>>=1,x=x*(ll)x%ha) if(y&1) an=an*(ll)x%ha;
return an;
}
vector<int> g[23];
int n,Q,root,ans[N],a[23],b[23],S,d[23];
bool bt[N];
void dfs(int x,int fa){
a[x]=d[x],b[x]=1; int tmp=1;
for(int i:g[x]) if(i!=fa){
dfs(i,x),ADD(tmp,ha-a[i]*(ll)d[x]%ha);
ADD(b[x],b[i]*(ll)d[x]%ha);
}
tmp=ksm(tmp,ha-2);
a[x]=a[x]*(ll)tmp%ha;
b[x]=b[x]*(ll)tmp%ha;
if((1<<x)&S) a[x]=b[x]=0;
}
inline void solve(){
bt[0]=1; for(int i=1;i<(1<<n);i++) bt[i]=!bt[i^(i&-i)];
for(int i=0;i<n;i++)
for(int j=(1<<n)-1;j>=0;j--) if(!((1<<i)&j)) ADD(ans[j|(1<<i)],ha-ans[j]);
for(int i=(1<<n)-1;i>=0;i--) if(bt[i]) ans[i]=ha-ans[i];
for(int k,s;Q;Q--){
scanf("%d",&k),s=0;
while(k--) s|=1<<read();
printf("%d\n",ans[s]);
}
}
int main(){
scanf("%d%d",&n,&Q),root=read();
int uu,vv;
for(int i=1;i<n;i++){
uu=read(),vv=read();
g[uu].pb(vv),g[vv].pb(uu);
d[uu]++,d[vv]++;
}
for(int i=0;i<n;i++) d[i]=ksm(d[i],ha-2);
for(S=1;S<(1<<n);S++){
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
dfs(root,-1),ans[S]=b[root];
}
solve();
return 0;
}
原文：https://www.cnblogs.com/JYYHH/p/9194873.html