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;
}