problem
根据 prufer 引理，有标号的无根树的种类是 \(n ^ {n-2}\)。
对于一棵 n 个节点的带权无根树，边权总是 +1 或者 -1。那么总共有 \(n^ {n-2} * 2 ^ {n-1}\) 种树。
其中，如果每个点相连的边的权重的乘积都是 -1 的话，我们说这是一棵美丽树。
然后问，所有 N 个节点的美丽树中，1 到 n 的距离 \(d_{1,n}\) 的和。五十万。
solution
定理一
若 \(n\) 为奇数，则答案为 \(0\)。
证明
考虑在实数域中 \(x^2\geq 0\)，但是如果你算一下奇数时所有边的乘积开个平方，这相当于 \((-1)^n\)，然而它 \(<0\)。
接下来只考虑 \(n\) 为偶数，
定理二
若树的形态固定，则边权也是固定的。
构造
考虑找到一片叶子，因为叶子只有一条边，所以直接给那条边赋权，然后砍掉叶子，继续递归。
定理十一万四千五百一十四
对于一条边，如果它左边有 \(L\) 个点，右边有 \(R\) 个点：
- \(L,R\) 奇偶性相同。
- 这条边的权值为 \((-1)^L=(-1)^R\)。
证明
归纳很容易的。
其实我们考虑一棵树，我们不妨抽象一点用 \(w_u\) 表示 \(u\to fa_u\) 的边的权值，它是 \(-\prod_v w_v\)，我们换种运算：\(1+\sum_v w_v \pmod 2\)，原来是子树大小和。
定理一百九十一万九千八百一十
对每条边分开考虑。考虑一条边在 \(1\to n\) 路径上的充要条件：\(1,n\) 各在它们两端。
故答案为 \(\sum_{1\leq i<n}(-1)^i\binom{n-2}{i-1}f(i)f(n-i)\)，其中 \(f(n)=n^{n-1}\) 是 \(n\) 个点有标号有根数的数量。
标签：题解,Sum,Tree,sum,权值,考虑,定理 From： https://www.cnblogs.com/caijianhong/p/solution-CF1762E.html