树链剖分模版1

题目描述:

你需要做出基础的树链剖分算法。

 

输入格式:

输入一棵以1为根的树。

第1行为结点数量N

接下来N行：第1个数为结点的子结点数量M，接下来M个数为子结点编号

输出格式:

第1行输出N个数，第i个数代表以i为根的子树大小

第2行输出N个数，第i个数代表i发出的重边的另一端编号，要尽量小，如果没有，输出0

 N<=100

样例输入:

5
2 2 4
1 5
0
1 3
0

样例输出:

5 2 1 2 1
2 5 0 3 0

提示:

以下内容摘自百度百科

常见的路径剖分的方法是轻重树链剖分启发式剖分
将树中的边分为轻边和重边 定义size(X)为以X为根的子树的节点个数。 令V为U的儿子节点中size值最大的节点那么边(U,V)被称为重边树中重边之外的边被称为轻边。

预处理
第一遍dfs求出其为根的子树大小size[x]
第二遍dfs
根节点为起点向下拓展构建重链
选择最大的一个子树的根继承当前重链
其余节点都以该节点为起点向下重新拉一条重链
给每个结点分配一个位置编号每条重链就相当于一段区间用数据结构去维护。
把所有的重链首尾相接放到同一个数据结构上然后维护这一个整体即可

时间限制: 1000ms
空间限制: 256MB

---