博客

spoj 1825

题目：http://www.spoj.com/problems/FTOUR2/

题目大意：给你一棵节点数为 N 的树，每条树枝有权值，点有黑白两色，问你找一条路径使其进过的黑色的节点数不超过 K 且权值和最大，然后输出这个权值。

思路：继上题的 Tree 之后，漆子超论文的下一道题目，表示看论文、题解和别人代码做了很久。。 = =

用G[ i ][ j ] 表示根节点 的第 i 个儿子经过的黑点数为 j 的最优值，但是 i、j 范围太大了，空间开不下。但是我们不需要保存所有的儿子对应的所有 j ，我们只关心已经算过的节点中每个 j 对应的最大值，所以这里需要优化一下：用f [ i ]  表示已处理的节点中黑点数不超过 i 的最优值，显然，f 具有单调递增性。然后对于当前要处理的节点，算出 g[ i ] ，,然后用g[ i ] 去和 f[ i ]组合更新 ans ，再更新 f[ i ] 就行了，注意：f[ i ]  更新好以后，也要用符合要求的 i 更新 ans ，因为 g[ i ] 有可能不和 f[ i ] 结合，即，根节点为路径的起点或终点。对于每一个根节点，需要对每个儿子按照 dep[ i ] 先进行排序，然后每次只要更新到dep[ i ] 就行了，时间复杂度为排序的复杂度O（NlogN），如果不排序，则最坏情况下，时间复杂度会达到  O（N^2 ）。

基本上是照着别人代码来的，先开始一直TLE，然后WA，然后RE，最后才 AC 的。。 = =  WA的原因在于，我把 solve（）里的 getted[ root ] =0， 写成 getted[ x ] =0 了。。 T T，而TLE是在于找 root 时，我是按照上一题的方法来的，代码是这样的：

int num[MAXN],maxv[MAXN];

vector <int> node;

void dfs(int u,int fa)
{
    node.push_back(u);
    num[u]=1;
    for(int e = head[u];e!=-1;e= edge[e].next)
    {
        int v = edge[e].t;
        if(getted[v]||v==fa) continue;
        dfs(v,u);
        num[u]+=num[v];