Z国的骑士团是一个很有势力的组织，帮会中汇聚了来自各地的精英。他们劫富济贫，惩恶扬善，受到社会各界的赞扬。
最近发生了一件可怕的事情，邪恶的 Y 国发动了一场针对 Z 国的侵略战争。战火绵延五百里，在和平环境中安逸了数百年的 Z 国又怎能抵挡的住 Y 国的军队。于是人们把所有的希望都寄托在了骑士团的身上，就像期待有一个真龙天子的降生，带领正义打败邪恶。
骑士团是肯定具有打败邪恶势力的能力的，但是骑士们互相之间往往有一些矛盾。每个骑士都有且仅有一个自己最厌恶的骑士（当然不是他自己），他是绝对不会与自己最厌恶的人一同出征的。
战火绵延，人民生灵涂炭，组织起一个骑士军团加入战斗刻不容缓！国王交给了你一个艰巨的任务，从所有的骑士中选出一个骑士军团，使得军团内没有矛盾的两人（不存在一个骑士与他最痛恨的人一同被选入骑士军团的情况），并且，使得这支骑士军团最具有战斗力。
为了描述战斗力，我们将骑士按照 1 至 n 编号，给每名骑士一个战斗力的估计，一个军团的战斗力为所有骑士的战斗力总和。
一共N有个骑士，每个骑士不能和另外某个骑士在一起，求最大战斗力。
根据题意，可以把骑士间的关系放到一个图上，把战斗力转化为点上的值，把A憎恨B转化一条A->B的边。于是，题意可以转换为：
在一个N个点的图里，选择若干个不联通的点，求值的最大和。
这是最暴力的方法（ \(O ( 2 ^ N * N ^ 2 )\) ），当然，也能拿到30%的分数是个好主意。
直接枚举每个点取不取，再进行判断，如果合法再计算战斗力总和，并更新答案。
#include <stdio.h>
int n, a [ 20 ], x;
bool map [ 20 ] [ 20 ];
inline int max ( int x, int y ) { return x > y ? x : y; }
bool check ( int sta ) {
for ( int i = 0; i < n; i ++ )
for ( int j = 0; j < n; j ++ )
if ( i != j && sta & ( 1 << i ) && sta & ( 1 << j ) && map [ i ] [ j ] )
return false;
return true;
}
int calc ( int sta ) {
int sum = 0;
for ( int i = 0; i < n; i ++ )
if ( sta & ( 1 << i ) )
sum += a [ i ];
return sum;
}
int main ( ) {
scanf ( "%d", & n );
for ( int i = 0; i < n; i ++ ) scanf ( "%d%d", & a [ i ], & x )， map [ i ] [ x - 1 ] = map [ x - 1 ] [ i ] = true;
int ans = 0;
for ( int sta = 0; sta < ( 1 << n ); sta ++ )
if ( check ( sta ) )
ans = max ( ans, calc ( sta ) );
printf ( "%d", ans );
return 0;
}
其实 你可能早就注意到了，这道题和 没有上司的舞会 很像。
但是 你也可能早就注意到了，这不是 树，而是 图。
你再仔细看看题，会发现这个图有 N个点N条边，比树正好多了一条，所以会有出现环（非自环）。
这个就是 基环树。
简单来说，基环树 就是树多了一条边，产生了环。
而在这道题中，还是一个特例，叫做 外向树，也就是每个点只有一条入边 所以才看起来很外向吗
找环其实可以用拓扑排序来做，然而在这道题中没有这个必要 并且我也不会写
所以，可以用DFS搞定：
int find_loop ( int u )
{
vis [ u ] = true;
if ( vis [ fa [ u ] ] ) ans = u;
else find_loop ( fa [ x ] );
}
由于多出了一个环，所以肯定要把环断开。
当然你肯定先想到把环上每条边依次断开来尝试，但根据上司聚会的求法，你会发现环上断开的位置其实无所谓。
其实对于环，我们可以像将一条边强行断开处理一遍，然后强行连上再处理一遍，这就是“二次DP法”
所以对于每一个基环树，可以找出环，在环上某个点强行把父节点连上，再强行把父节点断开，两次上司聚会求最值。
#include <stdio.h>
const int MaxN = 1000001;
int n, parent [ MaxN ]; long long a [ MaxN ];
int head [ MaxN ], next [ MaxN ], vect [ MaxN ], edgenum;
bool vis [ MaxN ];
long long f [ MaxN ] [ 2 ];
long long ans, ans1, ans2; int node;
inline long long max ( long long x, long long y ) { return x > y ? x : y; }
inline void addedge ( int u, int v );
inline int find_loop ( int u );
inline void dfs ( int u );
int main ( )
{
scanf ( "%d", & n );
for ( int i = 1; i <= n; i ++ ) scanf ( "%lld%d", & a [ i ], & parent [ i ] )， addedge ( parent [ i ], i );
for ( int i = 1; i <= n; i ++ )
if ( ! vis [ i ] )
{
node = find_loop ( i )，dfs ( node )，ans1 = max ( f [ node ] [ 0 ], f [ node ] [ 1 ] ); //强行断开
node = parent [ node ]，dfs ( node )，ans2 = max ( f [ node ] [ 0 ], f [ node ] [ 1 ] ); //强行连上
ans += max ( ans1, ans2 );
}
printf ( "%lld", ans );
return 0;
}
inline void addedge ( int u, int v )
{
edgenum ++;
vect [ edgenum ] = v ，next [ edgenum ] = head [ u ]，head [ u ] = edgenum ;
}
inline int find_loop ( int u ) //找环
{
vis [ u ] = true;
if ( vis [ parent [ u ] ] ) return u;
else return find_loop ( parent [ u ] );
}
inline void dfs ( int u ) //上司聚会稍稍修改
{
vis [ u ] = true ，f [ u ] [ 1 ] = a [ u ]，f [ u ] [ 0 ] = 0; //一定要在vis上标记
for ( int e = head [ u ]; e; e = next [ e ] )
{
int v = vect [ e ];
if ( v == node ) f [ v ] [ 1 ] = -1; //如果是拆开的边，就不遍历
else
{
dfs ( v, node );
f [ u ] [ 0 ] += max ( f [ v ] [ 0 ], f [ v ] [ 1 ] )， f [ u ] [ 1 ] += f [ v ] [ 0 ];
}
}
}
这个代码可以在Luogu上卡过，然而在诚享OJ上会TLE 10%，这说明 诚享OJ太垃圾了 这个代码还不够优化。
然而在思路上好像也优化不到哪里去了（请总时间1000ms的DaLao们多多指教）
于是我们就需要做一些丧心病狂的卡常优化
注意：这里的代码做了非常丧心病狂的优化，不保证正确性
#pragma GCC optizime(3)
#include <stdio.h>
bool vis [ 1000001 ];
int n, a [ 1000001 ], parent [ 1000001 ], root, head [ 1000001 ], next [ 1000001 ], vect [ 1000001 ], edgenum;
long long f [ MaxN ] [ 2 ], ans, ans1, ans2;
inline int read(){register int s=0;register char ch=0;while(ch<48||ch>57)ch=getchar();while(ch>=48&&ch<=57)s=s*10+ch-48,ch=getchar();return s;} //标准快读
inline long long max(long long x,long long y){return x^((x^y)&-(x<y));} //位运算比较
void dfs ( int u )
{
* ( vis + u ) = 1，f [ u ] [ 1 ] = * ( a + u )，f [ u ] [ 0 ] = 0; //丧心病狂数组访问
for ( register int e = * ( head + u ); e; e = * ( next + e ) ) { //丧心病狂register
register int v = * ( vect + e );
if ( v == root ) f [ v ] [ 1 ] = -1;
else dfs ( v )，f [ u ] [ 0 ] += max ( f [ v ] [ 0 ], f [ v ] [ 1 ] )，f [ u ] [ 1 ] += f [ v ] [ 0 ];
}
}
int main ( )
{
n = read ( );
for ( register int i = 1; i <= n; i = - ~ i ) { //丧心病狂++：-~
* ( a + i ) = read ( )，* ( parent + i ) = read ( );
edgenum = - ~ edgenum，* ( vect + edgenum ) = i，* ( next + edgenum ) = * ( head + * ( parent + i ) )，* ( head + * ( parent + i ) ) = edgenum;
}
for ( register int i = 1; i <= n; i = - ~ i )
if ( ! * ( vis + i ) ) {
* ( vis + i ) = 1，root = i;
while ( ! * ( vis + * ( parent + root ) ) ) root = * ( parent + root )，* ( vis + root ) = 1; dfs ( root )，ans1 = max ( f [ root ] [ 0 ], f [ root ] [ 1 ] );
root = * ( parent + root )，dfs ( root )，ans2 = max ( f [ root ] [ 0 ], f [ root ] [ 1 ] );
ans += max ( ans1, ans2 );
}
printf ( "%lld", ans );
return 0;
}
这道题引入了一个新的结构——基环树。其实没必要了解这个名字，自己也也已发明出来算法。
当然，在想不出来时，暴力也是个好方法，至少能拿30%的分数
原文：https://www.cnblogs.com/wukaixuan/p/12728243.html