[HOJ 136][IOI 2007]Training

HOJ生病惹QQ，因此我在這裡做了題目備份，請參考～

換句話說，題目希望不產生偶環的前提下，總權重最大化
感覺會超多奇環相互交錯再一起耶......好複雜QQ

我們先來討論兩個奇環的情況
1. 不相交：合法情況，之後再深入討論
2. 相交於一點：合法情況，之後再深入討論
3. 重合於任何邊：形成偶環了，不合法！
(原來奇環也只有這樣嘛www)

那些會在樹上形成偶環的非樹邊可以直接刪除了

我們來嘗試構造一個樹形$DP$
首先，我們必須避免同一條邊被多個環同時使用
因此，狀態中必須包含哪些邊被用過了
由於每個點的度數不超過$10$
因此我們可以利用位元壓縮的技巧，用$DP[u][s]$代表以$u$為節點的子樹中，連到$u$的邊 (包含樹邊和非樹邊) 的子集合$s$ (用$bit\ mask$表示) 被用過了，總權重最多多少

於是，我們可以枚舉所有「樹上路徑」會通過$u$的邊$e$，然後用以下方式直接算出每個$DP[u][s]$：

圖片來源：http://www.ioinformatics.org/locations/ioi07/contest/solutions.pdf

其中除了以下這個 (稱作$subtree$) 需要遞迴計算之外，其他的都已經在先前遞迴到子樹時計算好了

可是這樣要計算$subtree$的時候還要想辦法把兩端都在$subtree$內的非樹邊分離出來
想一想複雜度好像很容易又爛掉了QQ

沒關係，不用遞迴了，我們先算好只加一個環的部分

然後依照$bit\ mask$中$1$的數量由小到大更新$DP[u]$ (這時候如果用到的邊沒有重複就可以直接相加來更新更大的$DP[u]$了)
為了節省時間，只更新「加一個環」(用掉兩條邊) 和「加一棵子樹」(用掉一條邊) 的情況，然後順著$DP[u]$的更新順序就可以把所有情況都考慮進去了

小提醒：請記得答案是所有邊的權重總和減掉算出來的$DP$

時間複雜度：$O(N^{2}+NM+2^{10}M)$ (預處理從$u$走到$v$要先走連到$u$的第幾條邊、預處理一條邊是$u$的第幾條邊、更新$DP$)

code:

請參考這裡