来源：CQ 省集。
[IOI2020 Day2] C. Stations
IOI2020 都是些什么人类在出？B. Counting Mushrooms
不过这题看着非常友善。
在幕后有一颗 \(n\) 个节点的树，点序号从 \(0 \sim n-1\)，边序号从 \(0 \sim n-2\)。
你需要实现如下两个函数：
int[] label(int n, int k, int[] u, int[] v)该函数读入 \(n,k\) 及长为 \(n-1\) 的数组 \(u,v\)，返回一个长为 \(n\) 的数组，表示：
- \(n\)：节点个数。
- \(k\)：返回值的所有元素最大值的上限。若超过上限，分数为 \(0\)；
- \((u_i,v_i)\) 给出树的每条边，连接序号为 \(u_i\) 与 \(v_i\) 的点。
- 返回值：对于序号为 \(i\) 的点，返回值的第 \(i\) 位表示它的编号（自拟），编号必须为非负整数。
int find_next_station(int s, int t, int[] c)该函数读入 \(s,t\) 及长为 \(n-1\) 的数组 \(c\)，返回一个整数值：
- \(s\)：出发点编号。
- \(t\)：目标点编号。
- \(c\)：\(s\) 的所有邻居的编号。
- 返回值：从 \(s\) 到 \(t\) 的路径上，\(s\) 的下一个点的编号。
- 该函数不能获取调用
label过程中修改的全局或静态变量。对于一个有 \(r\) 组测试用例的数据点：
- 交互程序先会调用恰好 \(r\) 次
label，每次传入不同的树。- 再对于每个不同的树，进行若干次
find_next_station的调用，传入的编号等于对应的label返回编号。\(2 \le n \le 1000\)，若想获得满分，你的编号不能超过 \(1000\)。
一棵树上的节点 \(s \to t\) 的路径，判断 \(s\) 的后继节点，需要哪些信息？
不妨钦定根为 \(0\)。
- \(s\) 与 \(t\) 的祖先关系：若 \(s\) 不为 \(t\) 的祖先，则后继节点为 \(\mathrm{fa}_s\)；
- 否则，看 \(t\) 位于哪一棵子树内：若 \(s\) 的子节点 \(x\) 满足 \(t\) 位于 \(x\) 子树内，则后继节点为 \(x\)。
容易发现祖先关系与子树关系是等价的，所以都其实是子树关系，而这个是易于使用 dfn 序来判断的。
- \(\mathrm{dfn}_{\mathrm{fa}_u} < \mathrm{dfn}_u\)，且是唯一一个邻居满足这个条件的。同一子树内，dfn 连续，所以可以用 dfn 区间判断祖孙关系。
- 问题在于并不知晓子树内 dfn 最大的点。
考虑一些等价的，可以使子树内编号连续的标号法。还要同时知道最大、最小标号。
题目给出了所有的邻居，这是很好的性质，但刚刚的 dfn 并没有把它利用完全。如果能够通过自己给出最大/最小，用儿子得出最小/最大，就可以同时知道子树对应的标号区间了。
这给了一个思路，交替标号最小最大。子树 \(u\) 要满足 \(u\) 的标号最小，那么就先行标号 \(u\)；如果要使 \(u\) 的编号最大，则遍历完子树最后标号 \(u\)。
为实现交替标号最大最小，采用黑白染色的方法，黑点先给自己标号，再进入子树给其他节点标号；白点先进入子树标号，最后给自己标号。
最后，设编号为 \(p_i\)，对于黑点 \(u\)，它的邻居全是白点，其子树编号区间就是 \([p_u,\displaystyle\max _{\mathrm{fa}_v=u}p_v]\)，同时要注意 \(p_{\mathrm{fa}_{u}} > p_u\)，且是最大的一个；还有特判没有父亲的 \(0\) 节点。
然后就完了哦吼吼。