P2607题解

建议先做P1352 没有上司的舞会树形dp板子题，有助于此题的完成。

题目大意

给你 $ n $ 个骑士，他们每人都有一个痛恨的人，不能和那个痛恨的人同时作战，当他作战时，他的战斗力是 \(a_{i}\) ，规划一种布兵方案使得军队战斗力最强。

分析

通过阅读题面，可以将这些骑士与他们痛恨人的关系化为一棵树，对于每个人，痛恨的人是他这个节点的父亲，于是，对于以下数据，问题出现了。

3
10 3
20 1
30 2

所有骑士形成了一个环，对于这种情况，我们就要破环。

此处做另外说明，对于一个有 \(n\) 边，有 \(n\) 个点的无根树，且每个节点都有父亲的情况下，这个树一定会出现环。

破环

破环操作，说白了就是在树上找环并从环上任意一个点切开进行两次树形dp。

于是我们可以写出以下代码

for(int i=1;i<=n;++i) {
    if(!v[i]) {
        find_c(i);
    }
}
//n是骑士的数量，v是访问标记，find_c是接下来要写的找环函数

意思就是对于每一个没有访问过的节点，都对它做一次找环操作。

这里再做一次说明，在此题中，因为每个节点都有父节点，所以任意一个节点 $ i ~ (1 i n)$ 没有被访问过时，将它作为无根树的根时，它必然在一个环中，所以当一个节点 $ i $ 不在之前的任意一个环中，它必然在一个新的环中。

找环操作可以参见以下代码，有注释

int root;//root为根
void find_c(int n) {
    root=n;
    v[root]=true;
    while(!v[gf[root]]) {
        //gf[i]指的是i的父节点，也就是i痛恨的人
        root=gf[root];
        v[root]=true;//标记
    }
    //跳出循环说明找到环
    dfs();//进行树形dp
}//找环函数

树形dp

这里几乎就是树形dp的模板了，只需要注意代码中的关键点。

int dp[Maxn][2]={};//第二维表示选或不选


void dfs2(int pt) {
    v[pt]=true;
    dp[pt][0]=0;
    dp[pt][1]=a[pt];//这位战士的战斗力
    for(int i=0;i<v[pt].size();++i) {
        if(v[pt][i]!=root) {//注意此处，从root处切开！！！
            dfs2(v[pt][i]);
            dp[pt][0]+=max(dp[v[pt][i]][1],dp[v[pt][i]][0]);
			dp[pt][1]+=dp[v[pt][i]][0];
        }
        else {
            dp[v[pt][i]][1]=-1<<20;
        }      
    }//访问所有的子节点    
}//树形dp模板

void dfs() {
    int ans=0;
    dfs2(root);
    ans=max(dp[root][0],dp[root][1]);
    root=gf[root];
    dfs2(root);
    sum+=ans;//sum是最后输出的答案
}
/*
简而言之，就是从root处切开使得树变为两个连通块，然后对两个连通块做树形dp；
最后在两个连通块中找最大战力即可。
*/