AC代碼

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

題意：

我們稱具有n個(gè)頂點(diǎn)的邊加權(quán)樹為好的，如果每條邊的權(quán)重為1或 ?1，

對(duì)于每個(gè)頂點(diǎn)i，以i為一個(gè)端點(diǎn)的所有邊的邊權(quán)重的乘積為?1.

給你一個(gè)正整數(shù)n。有n^(n?2)?2^(n?1）個(gè)不同邊加權(quán)樹，n個(gè)頂點(diǎn)編號(hào)從1到n，

使得每條邊加權(quán)為1或?1.你的任務(wù)是找到所有這些好樹的d(1，n)之和。

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

兩棵樹被認(rèn)為是不同的，如果：

存在兩個(gè)頂點(diǎn)，使得在其中一棵樹中它們之間有一條邊，而在另一棵樹上沒有。

存在兩個(gè)頂點(diǎn)，使得在兩棵樹中它們之間都有一條邊，但是一棵樹中它們之間的邊的權(quán)重不同于另一棵樹。

d(u，v)表示從u到v的唯一簡(jiǎn)單路徑上所有邊的權(quán)重之和。

題解：

組合數(shù)學(xué) + 樹

n=4時(shí)，解釋 -1 for 8 trees:?

其中2條路徑長(zhǎng)度為3，且2次路過邊權(quán)重-1；

其余6條路徑長(zhǎng)度為1，且1次路過邊權(quán)重-1，這其中星型結(jié)構(gòu)2種情形：分別是頂點(diǎn)1是葉子，和頂點(diǎn)1是中心點(diǎn)；

其余4條路徑長(zhǎng)度為1，且1次路過邊權(quán)重-1，均是一條路的樹形結(jié)構(gòu)：

2種情形：頂點(diǎn)1是葉子，頂點(diǎn)2和頂點(diǎn)3分別是另一個(gè)葉子；

2種情形：頂點(diǎn)4是葉子，頂點(diǎn)2和頂點(diǎn)3分別是另一個(gè)葉子.