快乐是短暂的，思考让我放下一切，AC的一瞬间还是很快乐的。
解题报告 https://codeforces.com/contest/1247/problem/F
我觉得这题想得出原理，但是写起来还是挺难的。
题：使用最少的步骤，从 bamboo tree 构造出 target normal tree。
存树
每个Node存next_brother，这个node的parent里面，存一个header。
相当于一个链表，文末代码一看便知。
原理1 目前在点p，那么 p->child1子树 和 p->child2子树 在bamboo tree中一定 是独立的
显而易见，在纸上举几个例子，会发现如果 两个子树分别包含的点 水乳交融的话，那么展开这个bamboo一定会耗费更多的步骤。
原理2 若在bamboo tree中，p->child1子树 在 p->child2子树 的前面，那么无论p->child1子树怎么排列，将p->child2提到目标位置的步骤是不变的
这个很关键，举例就是，现在有一颗树如图
针对Node1这个子树，假设现在bamboo tree上面，已经把node1这个子树defragment完成了。在bamboo tree中，“Node1子树”后面接“Node2子树”，如图，蓝色的是等待放置的下一个点
我们发现：无论Node1子树内部如何排列，把 “Node2子树” levitate to “Node1节点兄弟” 的位置，所需要的步骤都是一样的。
那么我们就已知了对于任意一个节点代表的子树：“把这个子树的点整理完” + “把附在这个segment后面的其他树升上去” 的步数 是相同的。
结论
所以我们就只需要针对所有的子树，来计算“仅仅整理这个子树”和“整理+浮起兄弟子树”的步骤分别是多少（代码中 ans_defrag_only 以及 ans_defrag_and_crawled）
然后我们针对每一个点，都尝试算一下哪个子树放到最后合适。
比如上面那个树，针对Node 0，显然Node 7子树放到bamboo的最后比较合适。
同理，根据上面的原理2，对于任何一个点Node p所代表的那一坨树，在bamboo tree中应该是
{p, [segment of p->child1], [segment of p->child2], ..., [segment of p->childtail]}
无论p->child1 \ p->child2 怎么排列，答案都是一样的。
代码如下，去掉注释打印整棵树：
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100010, MAXANS = 1000100;
struct Tree {
int parent = -MAXN;
int chhead = -1, bro = -1;
int ans_defrag_and_crawled, ans_defrag_only;
int ans_child_tail = -1;
}tree[MAXN];
void appendChild(int fn, int cn) {
tree[cn].parent = fn;
tree[cn].bro = tree[fn].chhead;
tree[fn].chhead = cn;
}
void dfs(int p) {
for (int ch = tree[p].chhead; ch != -1; ch = tree[ch].bro)
dfs(ch);
//ans defragment and crawled: defragment all of its subtree + send the 'visiter' as its brother.
tree[p].ans_defrag_and_crawled = 0;
for (int ch = tree[p].chhead; ch != -1; ch = tree[ch].bro)
tree[p].ans_defrag_and_crawled += tree[ch].ans_defrag_and_crawled; // let child's head to last_child's tail one by one.
tree[p].ans_defrag_and_crawled++; //send the 'visiter' from its child as its bro, level up +1.
//ans defragment only: don't have 'visiter', only tidy up all of its subtree
//ans_defrag_only = min{ child[i].defrag_only + child[other].defrag_and_crawled };
int sum = tree[p].ans_defrag_and_crawled - 1;
tree[p].ans_defrag_only = MAXANS;
for (int ch = tree[p].chhead; ch != -1; ch = tree[ch].bro)
if (tree[p].ans_defrag_only > sum - tree[ch].ans_defrag_and_crawled + tree[ch].ans_defrag_only) {
tree[p].ans_defrag_only = sum - tree[ch].ans_defrag_and_crawled + tree[ch].ans_defrag_only;
tree[p].ans_child_tail = ch;
}
if (tree[p].chhead == -1) //special case for leaf node.
tree[p].ans_defrag_only = 0;
}
int ans_bamboo[MAXN], ans_bamptr = 0;
int ans_op[MAXANS], ans_opptr = 0;
void write_levitate_op(int p, int now_parent) {
int target_parent = tree[p].parent;
// cout<<"LEVITATE "<<p<<" from "<<now_parent<<" to "<<target_parent<<endl;
while(now_parent != target_parent) {
ans_op[ans_opptr++] = p;
now_parent = tree[now_parent].parent;
}
}
void output(int p) {
// cout<<"Node "<<p<<": ans_defrag_only="<<tree[p].ans_defrag_only<<" ans_defrag_and_crawled="<<tree[p].ans_defrag_and_crawled<<endl;
// cout<<"\ttail_chid="<<tree[p].ans_child_tail<<endl;
ans_bamboo[ans_bamptr++] = p;
for (int ch = tree[p].chhead; ch != -1; ch = tree[ch].bro)
if (ch != tree[p].ans_child_tail) {
write_levitate_op(ch, ans_bamboo[ans_bamptr-1]);
output(ch);
}
if (tree[p].ans_child_tail != -1) {
write_levitate_op(tree[p].ans_child_tail, ans_bamboo[ans_bamptr-1]);
output(tree[p].ans_child_tail);
}
}
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int n;
cin>>n;
for (int i=1; i<n; i++) {
int nodeid;
cin>>nodeid;
appendChild(nodeid, i);
}
dfs(0);
output(0);
for (int i=0; i<ans_bamptr; i++)
cout<<ans_bamboo[i]<<" ";
cout<<endl;
cout<<ans_opptr<<endl;
for (int i=0; i<ans_opptr; i++)
cout<<ans_op[i]<<" ";
cout<<endl;
return 0;
}