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