P3995 树链剖分

树链剖分，计算机术语，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、SBT、SPLAY、线段树等）来维护每一条链。(摘自百度百科)

大宁最近在研究树链剖分。他发现树链剖分的时间复杂度主要由轻重链的划分方式保证，最常见的剖分方式是按照子树大小剖分。如图（摘自百度百科），黑边为重链，长度任意，白边为轻链，长度全部为1。注意，下图 1-2, 1-3 为不同轻链。  其中对于每个节点，其在重链上的儿子叫做重儿子，且只有唯一一个，而叶子节点没有重儿子。例如对于图上 1 号点，重儿子是 4 号点。显然，对于不同剖分方式，同一组查询访问的链的数量不同。现在给定一棵根为 1 号节点的有根树和若干询问操作，每次询问访问从 $u$ 到 $v$ 上面的所有轻重链一次。例如在上图的剖分方式中，查询 3 到 8 一共访问了 3 条：轻链 1-3，重链 1-4，轻链 4-8；查询 3 到 11 一共访问了 3 条：轻链 1-3，轻链 1-2，重链 2-11。 大宁请你给出一种剖分方案，使所有询问操作总共访问的**轻重链总条数**最小，由于可能有许多合法方案，请任意输出一种，我们提供Special Judge检验你的方案的正确性。 设你的剖分方式的查询链数为 $x$，std 答案的查询数为 $x_0$，评分参数为 $a$ 。 你得到的分数是： * $10$ 分 当 $x\leq x_0$ 。 * $8$ 分 当 $0

无

无

样例即为上图，但图上的剖分方式对于此处的查询并非最优。 对于 $20\%$ 的数据，$n,q