太困了，切了两题就睡了。
哦不不不这无疑是困难的，看到这题我无疑是害怕的。
听机房同学讲题，听懂了。
考虑以 nnn 为根，其余奇偶分组，每一组都直接接在 nnn 下面。此时每一个贡献路径都要经过 nnn，所以答案为所有点的深度和的两倍。显然这么构造上下界都能取到。
令点较多的组为 S1S_1S1 ，较少的组为 S2S_2S2 （upd：这个 S1,S2S_1,S_2S1 ,S2 大小疑似没关系），因此我们需要构造 ∑depS1,i+∑depS2,i=k2\sum dep_{S_{1,i}}+\sum dep_{S_{2,i}}=\frac{k}{2}∑depS1,i +∑depS2,i =2k 。
随便构造一组 x,yx,yx,y，使得 x+y=k2,x≥∣S1∣,y≥∣S2∣,x≤∣S1∣(∣S1∣+1)2,y≤∣S2∣(S2∣+1)2x+y=\frac{k}{2},x\ge |S_1|,y\ge |S_2|,x\le \frac{|S_1|(|S_1|+1)}{2},y\le \frac{|S_2|(S_2|+1)}{2}x+y=2k ,x≥∣S1 ∣,y≥∣S2 ∣,x≤2∣S1 ∣(∣S1 ∣+1) ,y≤2∣S2 ∣(S2 ∣+1) ，然后让 ∑depS1,i,∑depS2,i\sum dep_{S_{1,i}},\sum dep_{S_{2,i}}∑depS1,i
,∑depS2,i 分别为 x,yx,yx,y 即可。
以 S1S_1S1 为例。
然后就简单了：我们首先弄成一个链，然后把叶子节点深度逐个减一，直到答案减到 xxx。这个可以 O(n)O(n)O(n) 实现。然后就做完了。
但我想不出来怎么办/jk
实现得有点史。
时间复杂度：O(∑n)O(\sum n)O(∑n)。
