CF1225F Tree Factory 题解
考虑不论怎么样，每个子树里边最长的链都会接在别的链下面，因为如果这条链不动，让别的链接过来一定不优。所以就直接按这个排序然后输出 dfs 序就行了。具体证明我也不会，就是考场猜了个结论。
点击查看代码
const int N=1e5+13;
int n,son[N],maxd[N],dfn[N],dfs_clock,fa[N],dep[N];
std::vector g[N],ans;
void dfs(int u){
dfn[++dfs_clock]=u;dep[u]=dep[fa[u]]+1;
for(auto v:g[u])if(v!=son[u])dfs(v);
if(son[u])dfs(son[u]);
}
int main(){
read(n);
for(int i=2;i<=n;++i){
int x;read(x);++x;
fa[i]=x;
g[x].pb(i);
}
for(int i=n;i>=2;--i){
maxd[i]=max(maxd[i],1);
if(maxd[fa[i]]