CF GYM 103102J

题目

每个点都有 \(\frac{1}{2}\) 的概率有宝藏，现在给出每个点与离它最远的宝藏的距离 \(d_i\)，求在此条件下每个点有宝藏的概率，输出宝藏编号 (以概率为第一关键字，编号为第二关键字升序排列)

题解

条件概率题。。设 \(P(A|B)\) 表示在 \(B\) 事件发生的情况下 \(A\) 事件发生的概率

现在知道了每个点与离它最远宝藏的距离，那么我们可以发现对于一个根 \(u\) 来说，所有 深度 \(>d_u\) 的一定都不可能有宝藏，且它限制了 深度 \(=d_u\) 的点集中一定至少有一个点有宝藏，假如不考虑其它点的限制，那么对于 深度 \( 的点，概率都不会受到 \(u\) 的限制 。

但现在有了其它点的限制，该怎么做？

有一个性质：树上一个点 \(u\) 到一个点集 \(S\) 中的点最远距离，一定是由 \(u\) 与 \(S\) 的直径端点 \(v_1,v_2\) 其中一个构成的。由此我们可以发现每个点的 \(d_i\) 值实际上只表示了它距离 宝藏点集 直径两个端点的最大值，那么直径的中点一定是 \(d_i\) 值最小的。

先考虑直径长度为偶数，即只有一个中点，\(d\) 数组中只有一个最小值。设这个点为 \(v\) ，将其当根，则它的限制为： 深度 \(=d_v\) 的点集中，至少有两个 不同 子树内的点有宝藏；\(< d_v\) 的点集，它们的 \(d\) 值肯定也都表示的是另一棵不同子树内 深度 \(=d_v\) 的点集至少有一个宝藏，这个限制被 \(v\) 的限制完全包含，所以不需要考虑；\(>d_v\) 的点集，情况同上。

这么一分类，可以发现 深度 \( 的点没有受到任何限制，概率仍然是 \(\frac{1}{2}\)，\(>d_v\) 的点概率也一定是 \(0\)，现在只需要考虑 \(=d_v\) 的点之间概率的大小关系。

可以发现，对于每个点 \(u\) ，设事件 \(A\) 为 “ \(u\) 点有宝藏，且除了该点所属子树之外，还有至少一棵另外子树 深度\(=d_v\) 的点处有宝藏”，事件 \(B\) 为 “至少有两个不同子树内的 深度\(=d_v\) 的点处有宝藏”，则 \(P(u)=\frac{P(A)}{P(B)}\) ，由于所有的点 \(P(B)\) 是一样的，所以只需要考虑 \(P(A)\) 的大小。

\(P(A)\) 可以拆成两部分来看 “ \(u\) 点有宝藏” 的概率仍然是每个点都一样，即 \(\frac{1}{2}\) 。那么概率的区别就在于 “还有至少一棵另外子树 深度\(=d_v\) 的点处有宝藏” 设 深度\(=d_v\) 的点的总个数为 \(sum\)，点 \(u\) 所属子树中 有 \(siz_u\) 个点 深度\(=d_u\) ，概率即为 \(1-(1-\frac{1}{2})^{sum-siz_u}\) ，由此可得 \(siz_u\) 越大，出现宝藏的概率越小。

直径长度为奇数，即有两个中点，与上面类似考虑即可。

PS：这道题由 点到点集最远距离 转化到了直径上的问题。。然后分析一下，奇奇怪怪的限制少了很多。。

const int N=3e5+5;
int n,x,y,a[N],id,minn=1e9,deep[N],flag,pre;
vi v[N],g[N],f[N],ans,cy;
vectorw;
void dfs(int u,int fa,int id){
	deep[u]=deep[fa]+1;
	if(deep[u]a[i]){
			minn=a[i];id=i;
		}
	}
	for(int i=1;i<=n;i++){
		if(minn==a[i] && id!=i)flag=1,pre=i;
	}
	if(flag){
		dfs(pre,id,pre);
		for(auto ta:f[pre]){
			w.pb(mp(f[pre].size(),ta));
		}
		memset(deep,0,sizeof(deep));
		dfs(id,pre,id);
		for(auto ta:f[id]){
			w.pb(mp(f[id].size(),ta));
		}
	}
	else{
		for(auto tmp:v[id]){
			dfs(tmp,id,tmp);
			for(auto ta:f[tmp]){
				w.pb(mp(f[tmp].size(),ta));
			}
		}
		if(minn==0)w.pb(mp(0,id));
		else ans.pb(id);
	}
	
	
	sort(w.begin(),w.end());
	sort(ans.begin(),ans.end());
	sort(cy.begin(),cy.end());
	for(auto ta:w){
		cout<