CF1770E

补题。记录一下这道比较典的 E。

首先最后一步是诈骗，实际上就是 $\dfrac{\sum\limits_{i\in a}\sum\limits_{j\in a\land j\not=i}dis(i,j)}{C_k^2}$。

然后考虑如果点固定怎么计算上面的式子。这是个很常见的 trick：枚举每条边算贡献，即记录一个点 $v$ 的子树内有多少个有标记的点 $c_v$，这个点连向父亲的边的贡献即为 $c_v\times(k-c_v)$。

考虑推广到有转移的情况。这里有一个关键的性质：$\Delta c_v$ 最大为 1，因为不在这条边上的点对 $c_v$ 明显没有贡献，而在这条边上的点最多只会产生 $1$ 的贡献。所以分 $u,v$ 有没有蝴蝶的情况讨论。设 $p_u$ 为 $u$ 点有蝴蝶的概率。则有：

• 都有标记：$p_u\times p_v\times c_v\times(k-c_v)$。即无论如何都不会对该边产生贡献。

• 都没标记：$(1-p_u)\times(1-p_v)\times c_v\times(k-c_v)$。同上。

• $u$ 有标记：$p_u\times (1-p_v)\times \dfrac{c_v\times(k-c_v)+(c_v+1)\times(k-c_v-1)}{2}$。即有 $0.5$ 的概率标记会从 $u$ 转移到 $v$。

• $v$ 有标记：$p_v\times (1-p_u)\times \dfrac{c_v\times(k-c_v)+(c_v-1)\times(k-c_v+1)}{2}$。同上。

然后还要处理标记转移后 $u,v$ 有标记的概率。也可以用类似上面的分类2方法计算。最后拆开化简得到 $p_u=p_v=\dfrac{p_u+p_v}{2}$。

枚举每条边转移即可。

code：

int n,m,c[N],p[N],dep[N];
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<1];
inline void add(int u,int v){
	e[++tot]={v,head[u]};
	head[u]=tot;
}
inline int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)
			ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;
		y>>=1;
	}
	return ret;
}
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==f)
			continue;
		dfs(v,u);
		c[u]+=c[v];
	}
}
void solve(){
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=m;i++){
		scanf("%d",&x);
		c[x]=p[x]=1;
	}
	for(int i=1,u,v;i<n;i++){
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
	const int inv=qpow(2,mod-2);
	int ans=0;
	for(int i=1;i<=tot;i+=2){
		int u=e[i+1].to,v=e[i].to;
		if(dep[u]>dep[v])
			swap(u,v);
		ans=(ans+1ll*(1ll*p[u]*p[v]%mod+1ll*(1-p[u]+mod)*(1-p[v]+mod)%mod)*c[v]%mod*(m-c[v])%mod//这里用了下分配律，没有影响
			+1ll*p[u]*(1-p[v]+mod)%mod*(1ll*c[v]*(m-c[v])%mod+1ll*(c[v]+1)*(m-c[v]-1)%mod)%mod*inv%mod
			+1ll*(1-p[u]+mod)*p[v]%mod*(1ll*c[v]*(m-c[v])%mod+1ll*(c[v]-1)*(m-c[v]+1)%mod)%mod*inv%mod)%mod;
		p[u]=p[v]=1ll*(p[u]+p[v])*inv%mod;//转移概率
	}
	printf("%lld\n",1ll*ans*qpow(1ll*m*(m-1)/2%mod,mod-2)%mod);
}