#樹形dp#洛谷 3687 [ZJOI2017]仙人掌

樹形dp

題目

給定一個簡單無向連通圖，問有多少種加邊方案使得這個圖變成簡單仙人掌。

分析

首先找到一棵生成樹，考慮其它非樹邊所對應的樹的路徑上的邊最多隻能用一次，

這可以用樹上差分做，如果一個點到其父節點的邊被用了多次就一定無解。

否則沒有被用過的部分将形成若幹棵樹，方案就是它們的乘積。

等于說問用若幹條路徑覆寫一棵樹的方案。

設 \(dp[x]\) 表示以 \(x\) 為根的子樹的方案數。

隻需要考慮 \(x\) 的鄰邊如何連接配接，子樹的答案直接相乘。

設 \(f[n]\) 表示 \(n\) 條邊任意比對的方案數，則

\(f[n]=f[n-2]*(n-1)+f[n-1]\)

那麼 \(dp[x]*=f[deg[x]]\)

代碼