GYM103102/SEERC2020 J One Piece
这题讲杂题的时候人没讲清楚,下来问做出来的大佬也没说清楚,网上翻半天题解一两句没了,心态炸了都。
题意略过,各位自己去看一遍原题目。
提前约定一些符号:\(\operatorname{dis}(a,b)\) 表示点 \(a,b\) 之间的距离。
首先我们设题目中给出的点 \(i\) 的最远距离为 \(a_i\)。
注意到只有一个宝藏的时候一定存在一个 \(a_i=0\),特判很好做,下面我们将这种情况剔除。
假设我们已经知道了宝藏点的情况,我们可以得到什么结论?
\(a_i\) 中最小值一定是这些宝藏中 最远的两个作为端点得到的链的中点(当然可能中点是在边上,这时两边的点同时取到最小值)。
为什么?其实还是比较显然,画一张图就基本看懂了:
红点有宝藏,黑点没有,中间那个实心红点就是中点,自己手模一下也就大概懂了。
严谨证明大概可以这么写:
假设存在一个 \(u\) 不为中点取到最小值,我们设距离它最远的这个宝藏点为 \(v\)。
此时一定存在另一个宝藏点 \(t\) 满足 \(u\) 到 \(t\) 的距离小于到 \(v\) 的距离,由于 \(u\) 不为中点,可知距离差至少为 \(2\),那就可以通过移动 \(u\) 使得 \(a_u\) 变小,因此 \(u\) 一定为中点。
这个时候我们就可以把这个中点拉出来单独看,设其为 \(p\)。
此时我们很容易知道与 \(p\) 的距离大于 \(a_p\) 的点的概率全为 \(0\),与 \(p\) 的距离小于 \(a_p\) 的点不受任何影响,自然全是 \(\frac{1}{2}\)。
哎,稍等,为什么不会有某些点限制住距离小于 \(a_p\) 的点概率为 \(0\),就像是下图这样呢?
实际上注意看,这种情况很显然不成立。
为什么?可以尝试一下标上所有点,会发现此时中点根本就不是上面那个点(按照前面图一的标法很容易看出来)。
严谨证明:
首先易得若存在一个点 \(x\) 使得 \(a_x\lt\operatorname{dis}(x,p)+a_p\),则点 \(x\) 会出现上图的情况(为什么我就不写了)。
然后我们从图一里面就能看出来,\(\forall y,a_y=\operatorname{dis}(y,p)+a_p\),这是因为距离点 \(y\) 最远的宝藏想要到一定要经过 \(p\),也就是一定在 \(p\) 的另一端,也就得到 \(\operatorname{dis}(y,p)+a_p\)。
为什么一定在 \(p\) 的另一端?这就很显然了,因为在这一端内得到的最远的宝藏一定可以映射到 \(p\) 的另一端一个和 \(p\) 等距离的宝藏,绕过 \(p\) 到那个宝藏一定是更远的。
得到这个结论,显然 \(a_x\lt\operatorname{dis}(x,p)+a_p\) 不成立。
现在我们回到正轨,预防你忘了,我再写一遍我们刚得到的结论:
与 \(p\) 的距离大于 \(a_p\) 的点的概率全为 \(0\)。与 \(p\) 的距离小于 \(a_p\) 的点不受任何影响,概率都是 \(\frac{1}{2}\)。
这之后我们需要特别关注 \(\operatorname{dis}(z,p)=a_p\) 的这些点 \(z\),它们比较特殊。
下面我们认为 \(z\) 是一类点的统称,这类点满足 \(\operatorname{dis}(z,p)=a_p\)。
注意到要保证 \(p\) 是中点这个条件成立,\(p\) 的各个子树中至少要有两个里面存在 \(z\)。
既然可能存在不合法的情况,直接就可以说其概率一定大于 \(\frac{1}{2}\),因为在所有的 \(z\) 都没被选的时候一定不合法,这个情况不存在,也就直接让所有 \(z\) 被选的概率大于 \(\frac{1}{2}\) 了。
那么这些 \(z\) 各自之间的概率如何比较?注意到每个情况出现的概率都是相等的,可以通过方案数来比较概率。
下面我们认为 \(p\) 为根,下述“子树”指 \(p\) 的儿子节点为根的子树。
假设对于某个点 \(z\),它被选择了,那么它这个子树里面选/不选都无所谓了,剩下在外面的点一定需要选至少一个,也就得到不合法方案数和所属子树大小有关,子树越大,不合法方案数越多。
给一张图就好理解了:
尝试计算实心红点的不合法方案数量,然后改变实心红点再算一下就明白了。
所以最后统计一下就做完了,给一份没有注释也毫无参考价值的代码吧:
#include<bits/stdc++.h>
using namespace std;
const int N=250010;
struct edge
{
int v,nex;
}e[N*2];
int fir[N],ent;
inline void add(int u,int v)
{
e[++ent]={v,fir[u]};
fir[u]=ent;
return;
}
int a[N],dep[N],siz[N];
struct Temp
{
int u,c;
bool operator < (const Temp &oth){if(siz[c]==siz[oth.c])return u<oth.u;return siz[c]<siz[oth.c];}
};
vector<Temp>point;
void DFS(int u,int f,int c)
{
if(dep[u]==a[c])
{
siz[c]++;
point.push_back({u,c});
dep[u]=-1;
return;
}
for(int i=fir[u];i;i=e[i].nex)
{
int v=e[i].v;
if(v==f)continue;
dep[v]=dep[u]+1;
DFS(v,u,c);
}
return;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
int mn=N;
for(int i=1;i<=n;i++)scanf("%d",a+i),mn=min(mn,a[i]);
if(mn==0)
{
for(int i=1;i<=n;i++)if(a[i]==0)printf("%d ",i);
for(int i=1;i<=n;i++)if(a[i])printf("%d ",i);
return 0;
}
int u=0,v=0;
for(int i=1;i<=n;i++)
{
for(int j=fir[i];j;j=e[j].nex)if(a[i]==mn&&a[e[j].v]==mn){u=i,v=e[j].v;break;}
if(u&&v)break;
}
if(u&&v)
{
dep[u]=dep[v]=1;
DFS(u,v,u),DFS(v,u,v);
}
else
{
for(int i=1;i<=n;i++)if(a[i]==mn)u=i;
dep[u]=1;
for(int i=fir[u];i;i=e[i].nex)dep[e[i].v]=2,DFS(e[i].v,u,e[i].v);
}
sort(point.begin(),point.end());
for(auto it:point)printf("%d ",it.u);
for(int i=1;i<=n;i++)if(dep[i]>0)printf("%d ",i);
for(int i=1;i<=n;i++)if(dep[i]==0)printf("%d ",i);
return 0;
}
标签:GYM103102,int,距离,SEERC2020,宝藏,Piece,中点,operatorname,dis
From: https://www.cnblogs.com/XiaoShanYunPan/p/17815265.html