AC代码

https://codeforces.com/contest/1762/submission/187569110

题意：

我们称具有n个顶点的边加权树为好的，如果每条边的权重为1或 −1，

对于每个顶点i，以i为一个端点的所有边的边权重的乘积为−1.

给你一个正整数n。有n^(n−2)⋅2^(n−1）个不同边加权树，n个顶点编号从1到n，

使得每条边加权为1或−1.你的任务是找到所有这些好树的d(1，n)之和。

由于答案可能非常大，您只需要找到它的模998244353。

两棵树被认为是不同的，如果：

存在两个顶点，使得在其中一棵树中它们之间有一条边，而在另一棵树上没有。

存在两个顶点，使得在两棵树中它们之间都有一条边，但是一棵树中它们之间的边的权重不同于另一棵树。

d(u，v)表示从u到v的唯一简单路径上所有边的权重之和。

题解：

组合数学 + 树

n=4时，解释 -1 for 8 trees: 

其中2条路径长度为3，且2次路过边权重-1；

其余6条路径长度为1，且1次路过边权重-1，这其中星型结构2种情形：分别是顶点1是叶子，和顶点1是中心点；

其余4条路径长度为1，且1次路过边权重-1，均是一条路的树形结构：

2种情形：顶点1是叶子，顶点2和顶点3分别是另一个叶子；

2种情形：顶点4是叶子，顶点2和顶点3分别是另一个叶子.