U219338 [USACO 2022 US Open Contest, G, P3] 平衡一棵树

Farmer John 对不同奶牛品种的进化进行了广泛的研究。所得到的结果形成一棵 $N$ 个结点的有根树，编号为 $1…N$，每个结点对应一个奶牛品种。对于每一个 $i\in[2,N]$，结点 $i$ 的父结点是结点 $p_i$，意味着品种 $i$ 是由品种 $p_i$ 进化而来的。称结点 $j$ 为结点 $i$ 的祖先，如果 $j=p_i$ 或者 $j$ 是 $p_i$ 的祖先。 树中的结点 $i$ 所关联的品种具有整数 $s_i$ 数量的斑点。定义树的「不平衡度」为所有结点对 $(i,j)$ 中 $\left | s_i-s_j \right |$ 的最大值，其中 $j$ 是 $i$ 的祖先。 Farmer John 不知道每个品种的 $s_i$ 的确切数值，但他知道这些值的下界和上界。你的任务是为每个结点分配一个整数值，以最小化树的不平衡度。

输入的第一行包含 $T$，为需要独立求解的子测试用例的数量，以及一个整数 $B$。 每个子测试用例的第一行包含 $N$，第二行包含 $N-1$ 个整数 $p_2,p_3,…,p_N$。 以下 $N$ 行每行包含两个整数 $l_i$ 和 $r_i$。 输入保证所有子测试用例的 $N$ 之和不超过 $10^5$。

对每个子测试用例，根据 $B$ 的值输出一行或两行。 每个子测试用例的第一行包含最小不平衡度。 如果 $B=1$，则再输出一行，包含 $N$ 个空格分隔的整数 $s_1,s_2,…,s_N$，为达到以上不平衡度的一种斑点数量的分配方式。任何合法的分配方式均正确。

【数据范围】 - $2\le N\le10^5$。 - $1\le p_i