考虑不论怎么样，每个子树里边最长的链都会接在别的链下面，因为如果这条链不动，让别的链接过来一定不优。所以就直接按这个排序然后输出 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=2;--i){
maxd[i]=max(maxd[i],1);
if(maxd[fa[i]]
Original: https://www.cnblogs.com/winterfrost/p/cf1225f-solution.html
Author: cunzai_zsy0531
Title: CF1225F Tree Factory 题解
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604289/
转载文章受原作者版权保护。转载请注明原作者出处！