一道挺综合的 hot tea,放到 PKUWC 的 D2T2 还挺喜闻乐见的(
首先我们考虑怎样对一个固定的集合 \(S\) 计算答案,注意到我们要求的是一个形如 \(E(\max(S))\) 的式子,套用 Min-Max 反演可将其转化为 \(\sum\limits_{T\subseteq S}(-1)^{|T|-1}E(\min(T))\),我们记 \(g_T=(-1)^{|T|-1}E(\min(T))\),那么 \(ans_S=\sum\limits_{T\subseteq S}g^T\),这东西显然是一个高维前缀和的形式,可以通过一遍 FWTor 求出(当然你叫它 SOS dp 我也没意见(
接下来考虑怎样计算 \(g_T\),也就等价于对所有集合 \(T\) 求出从 \(x\) 开始期望随机游走多少次就会走到 \(T\) 中的点。一个很显然的想法是写出一个 \(dp\) 式子然后暴力高斯消元,设 \(dp_{S,i}\) 表示从 \(i\) 开始走到 \(S\) 中的点的期望步数,显然若 \(i\in S,dp_{S,i}=0\),否则 \(dp_{S,i}=1+\dfrac{1}{deg_i}(\sum\limits_{(i,u)\in E}dp_{S,u})\),时间复杂度 \(2^nn^3\approx 10^9\),一脸过不去。考虑优化,注意到这题的图是一棵树,也就是说我们可以利用树的特殊性质进行 树形 \(dp\) instead of 高斯消元,如果没见过这个套路的可以去康康这个题或者这个题。具体来说我们还是设 \(dp_{S,i}\) 表示从 \(i\) 开始走到 \(S\) 中的点的期望步数,然后以 \(x\) 为根开始一遍 DFS,记 \(f\) 为 \(S\) 的父亲,那么 \(dp_{S,u}=1+\dfrac{1}{deg_u}(dp_{S,f}+\sum\limits_{v\in son_u}dp_{S,v})\),不难发现 \(dp_{S,u}\) 可以表示为 \(dp_{S,f}\) 的若干倍加上一个与 \(dp_{S,v}\) 有关的式子,其中 \(v\) 为 \(u\) 的子节点,我们不妨设 \(dp_{S,u}=K_udp_{S,f}+B_u\),那么有 \(dp_{S,u}=1+\dfrac{1}{deg_u}(dp_{S,f}+\sum\limits_{v\in son_u}(K_vdp_{S,u}+B_v))\),等式左右两边同乘 \(deg_u\) 可得 \(deg_udp_{S,u}=deg_u+dp_{S,f}+\sum\limits_{v\in son_u}(K_vdp_{S,u}+B_v)\),再把里面 \(\sum\) 拆开,里面与 \(dp_{S,u}\) 有关的项弄到左边可得 \((deg_u-\sum\limits_{v\in son_u}K_v)dp_{S,u}=dp_{S,f}+deg_u+\sum\limits_{v\in son_u}B_v\),再将左边除过去可得 \(dp_{S,u}=\dfrac{1}{deg_u-\sum\limits_{v\in son_u}K_v}dp_{S,f}+\dfrac{deg_u+\sum\limits_{v\in son_u}B_v}{deg_u-\sum\limits_{v\in son_u}K_v}\),故 \(K_u=\dfrac{1}{deg_u-\sum\limits_{v\in son_u}K_v}\),\(B_u=\dfrac{deg_u+\sum\limits_{v\in son_u}B_v}{deg_u-\sum\limits_{v\in son_u}K_v}\),DFS 求解即可,时间复杂度 \(2^nn\)。据说这玩意儿有个名字叫树上高斯消元,orzorz。
const int MAXN=18;
const int MAXP=1<<18;
const int MOD=998244353;
int n,qu,r,hd[MAXN+2],to[MAXN*2+5],nxt[MAXN*2+5],ec=0;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
int qpow(int x,int e=MOD-2){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int a[MAXN+2],b[MAXN+2],deg[MAXN+2];
void dfs(int x,int f,int S){
if(S>>(x-1)&1) return;int suma=0,sumb=0;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f) continue;
dfs(y,x,S);suma=(suma+a[y])%MOD;sumb=(sumb+b[y])%MOD;
} int inv=qpow((deg[x]-suma+MOD)%MOD);
a[x]=inv;b[x]=1ll*inv*(sumb+deg[x])%MOD;
}
int ret[MAXP+5];
void FWTor(int *a,int len){
for(int i=2;i<=len;i<<=1)
for(int j=0;j<len;j+=i)
for(int k=0;k<(i>>1);k++)
a[(i>>1)+j+k]=(a[(i>>1)+j+k]+a[j+k])%MOD;
}
int main(){
scanf("%d%d%d",&n,&qu,&r);
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);deg[u]++;deg[v]++;
adde(u,v);adde(v,u);
}
for(int i=0;i<(1<<n);i++){
memset(a,0,sizeof(a));memset(b,0,sizeof(b));
dfs(r,0,i);int cnt=__builtin_popcount(i);
ret[i]=((cnt&1)?b[r]:(MOD-b[r])%MOD);
} FWTor(ret,1<<n);
while(qu--){
int k,msk=0;scanf("%d",&k);
for(int i=1,x;i<=k;i++) scanf("%d",&x),msk|=(1<<x-1);
printf("%d\n",ret[msk]);
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章