【LOJ2542】【PKUWC2018】—随机游走（Min-Max容斥+树形dp）

传送门

容斥好题

---

考虑经过一个点集所有点的期望不好处理
我们考虑$min-max$容斥
则$ans=sum_{Tsubseteq S}E(min(T))$

现在我们先考虑怎么对于一个集合$T$求出有一个被访问的期望
令$f[i]$表示点$i$走到$T$中的点的期望步数,$in[u]$表示$u$的度数

则$f[u]=egin{cases} 0 & uin T\ (f[fa[u]]+1+sum_{v=son[u]}(f[v]+1))/in[u] & otherwise end{cases}$

高斯消元肯定是行不通的

而这中问题有个手动消元技巧：

对于叶子节点,其期望就是$f[fa[u]]+1$
只和父亲有关了，后面一项是一个常数

考虑对于$u$
有柿子$f[u]*in[u]-in[u]-sum_{v=son[u]}f[v]=f[fa[u]]$
$f[u]$只和$fa[u]$和$v$有关
考虑$f[v]$，只和$u$和$son[v]$有关……
一直到边界时$(xin T)$或$x$为叶子节点时，就只和$fa[x]$有关了（假装0也有关）

假设关系为$f[x]=A*f[fa[x]]+B$
那对于$y=fa[x]$来说,就变成了
$f[y]*in[y]-sum_{x=son[y]}A_x*f[y]-sum_{x=son[y]}B_x=f[fa[y]]$
也就是$A*f[y]+B=f[fa[y]]$
换一下就又是$f[y]=frac{f[fa[y]]}{A}+frac B A ightarrow A*f[fa[y]]+B$的形式！
那这样就可以一步步回带，知道对于$rt$
就是$A*f[rt]+B=0，（rt$没有父亲,右边就是$0）$
就可以解出起点出发的期望了
复杂度是$O(n)$的

对$2^n$个集合分别做一次就得到所有集合的$E(min)$了
考虑对于一个询问点集$S$,我们要枚举其所有子集求和

考虑$FWT$预处理出所有集合的答案，$O(1)$回答

时间复杂度$O(n2^n)$

#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<21|1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
} 
#define gc getchar
inline int read(){
	char ch=gc();
	int res=0,f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
	return f?res:-res;
}
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define re register
const int mod=998244353;
const int N=20,M=1<<20;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline void Add(int &a,int b){a=add(a,b);}
inline int dec(int a,int b){return a>=b?a-b:a-b+mod;}
inline void Dec(int &a,int b){a=dec(a,b);}
inline int mul(int a,int b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(res=mul(res,a));return res;}
vector<int> e[N];
int cnt[M],ans[M],f[M],in[N];
struct coef{
	int x,y;
	coef(int _x=0,int _y=0):x(_x),y(_y){}
	friend inline coef operator +(const coef &a,const coef &b){
		return coef(add(a.x,b.x),add(a.y,b.y));
	}
	friend inline coef operator -(const coef &a,const coef &b){
		return coef(dec(a.x,b.x),dec(a.y,b.y));
	}
	friend inline coef operator *(const coef &a,const int &b){
		return coef(mul(a.x,b),mul(a.y,b));
	}
};
int n,q,rt,sta;
coef dfs(int s,int u,int fa){
	if(s&(1<<(u-1)))return coef();
	coef now(in[u],dec(0,in[u]));
	for(int &v:e[u])
		if(v!=fa)now=now-dfs(s,v,u);
	int inv=ksm(now.x,mod-2);
	return coef(inv,mul(dec(0,now.y),inv));
}
int main(){
	n=read(),q=read(),rt=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		e[u].pb(v),e[v].pb(u);
		in[u]++,in[v]++;
	}sta=1<<n;
	for(int i=1;i<sta;i++)
		for(int j=0;j<n;j++)
		if(i&(1<<j))cnt[i]++;
	for(int i=1;i<sta;i++)
		f[i]=dfs(i,rt,0).y;
	for(int i=1;i<sta;i++)
		if(!(cnt[i]&1))f[i]=dec(0,f[i]);
	for(int i=0;i<n;i++)
	for(int j=0;j<sta;j++)
		if(j&(1<<i))Add(f[j],f[j^(1<<i)]);
	while(q--){
		int k=read(),s=0;
		for(int i=1;i<=k;i++)
			s|=(1<<(read()-1));
		cout<<f[s]<<'
';
	}
}