主要思路
首先，\(n – 1\) 个二元组代表着这颗树形有向图的形状。我们先考虑外向树的情况：子树根的时间戳要早于所有的子节点，所以可以考虑直接用背包的方法进行合并。如果有反向边，那么我们可以考虑进行容斥，枚举反向关系数再乘上一个容斥系数 \(-1\) 即可。
首先，\(n – 1\) 个二元组代表着这颗树形有向图的形状。我们先考虑外向树的情况：子树根的时间戳要早于所有的子节点，所以可以考虑直接用背包的方法进行合并。如果有反向边，那么我们可以考虑进行容斥，枚举反向关系数再乘上一个容斥系数 \(-1\) 即可。
这转化也真是妙…
首先，我们把 \((-1)^b\) 进行转换。发现转换成跟数论相关：\((-1)^b = 1 – 2(b \bmod 2)\)，则可以把这个式子弄一下：
想了半天都不知道怎么刻画状态，后面发现可以转成一个泛化问题，就比较好理解了。
考虑不严格地减去最小值、而是任意值，并达到题目要求的结果。这个问题肯定不会更优，而最优解可以直接作为本题最优解。
为啥我看到了 C# 代码（那是我逝去的青春）。
首先知道肯定是 SAM，但是你我都知道在线性构造的时候树的形态会变，所以没法维护根点权值和。所以加上一个 LCT 弄一下即可。
主要还是需要注意设计状态。
我们称 \((-1, x)\) 为单对，称 \((-1, -1)\) 为双对。我们可以试着从大到小填数字，这样就可以避免取 \(\min\) 的问题了。考虑 \(dp[i][j][k]\) 为选到第 \(i\) 个数字，然后有 \(j\) 个待处理、\(k\) 个单对待处理。转移的话，可以试着进行讨论。如果这个数字是某个单对之一，那么一种方式是啥都不干，还有一种是尝试进行匹配，\(j -= 1\)。如果不是单对之一，那么要么匹配、要么晾着。
最后乘上一个双对个数的阶乘，使其有序。
比较显然，我们需要选两个点集，最后贡献就是两个点集的极差积。排个序，并且把每个长度为 \(n\) 的区间都给做一遍即可。