傳送門

http://www.spoj.com/PRoblems/FTOUR2/en/

題目大意

給出一棵樹，其中每一節點都有一個顏色(黑色或白色)，每條邊都有一個權值，現要求在樹中找出一條鏈，使得鏈上的黑點數不超過給定的數k$k$ ，求權值和最大

我的想法

國家集訓隊論文 ： http://wenku.baidu.com/view/8861df38376baf1ffc4fada8.html 對鏈的操作可以想到用點分治。 如果一條鏈不包括當前(根)節點的話，就遞歸好了 如果包括根節點，那就把那條鏈從根節點劈開，剩下的兩段一定在不同的子樹中(如果這條鏈的一個端點就是根節點的話那就說另一段在某子樹中長度為0)，這要也可以保證不會算出不合法的情況。 然后我就這么劈開，提交，TLE 因為在遞歸子樹的時候有講究，令d(i)$d(i)$ 表示第i$i$ 棵子樹中的包含最多黑色節點的鏈的黑色節點數，如果d(i)>k$d(i)>k$ ，令d(i)=k$d(i)=k$ ，因為如果一條鏈包含了多于k$k$ 個黑色節點的話肯定不合法，然后先從小的d(i)$d(i)$ 入手遞歸，在遞歸大的。 再提交，WA 因為我忽略了根節點是黑色的情況 繼續提交，WA 因為k?d(i)?black(u)$k-d(i)-black(u)$ 在d(i)=k$d(i)=k$ 且u$u$ 是黑色節點的時候成了負數 越錯越勇，WA 因為在當兩顆子樹的黑點數加起來都小于k$k$ 的時候k?d(i)?black(u)$k-d(i)-black(u)$ 是沒有意義的，于是我把它改成min(d(j),k?d(i)?black(u))$min(d(j),k-d(i)-black(u))$ 第5次提交，WA 很多變量沒有初始化，就比如說遞歸子樹的時候d[]$d[]$ 沒有清0，找重心的時候子樹大小是錯的.. 最后第8次才A

代碼