题目大意
Z国要组织一支骑士团要参加一场战斗，每位骑士有一定的战斗力，同时每位骑士也有一个最厌恶的骑士（不是自己）。
要求选出一只骑士团，团中没有存在矛盾的两人（不存在一个骑士与他最厌恶的骑士一同被选入骑士团的情况），同时骑士团拥有最强战斗力。
分析
由于每位骑士只有一个厌恶的骑士，所以我们考虑连一条被厌恶骑士指向该骑士的有向边。这样就会形成若干个连通块，每个连通块均为基环树，且不存在指向环的边。
然后对于每个连通块，先找到环的位置，然后删去环的一条边（形成树形结构），删去的边上的两点记作a和b，以不选用a骑士和不选用b骑士分别做一次树形dp，得到最大战斗力。将每个连通块的最大战斗力相加，得到答案。
#include#include #include #include #include #include using namespace std;#define ll long long#define inf 0x7fffffff#define N 1000005int n, m, a, b;int val[N], vis[N], fa[N];ll ans, f[N][2];vector g[N];ll maxx(ll p, ll q) { if (p > q) return p; return q;}void find(int x) { vis[x] = 1; a = x; while(!vis[fa[a]]) { a = fa[a]; vis[a] = 1; } b = fa[a];}void dfs(int x) { vis[x] = 1; if (x != a && x != b) f[x][0] = 0, f[x][1] = val[x]; for (int i = 0; i < g[x].size(); i++) { int to = g[x][i]; if (to == a) continue; dfs(to); f[x][0] += maxx(f[to][0], f[to][1]); f[x][1] += f[to][0]; }}int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d%d", val + i, &m); g[m].push_back(i); fa[i] = m; } for (int i = 1; i <= n; i++) if (!vis[i]) { ll now = 0; find(i); f[a][0] = 0; f[a][1] = val[a]; f[b][0] = f[b][1] = 0; dfs(a); now = maxx(f[a][0], f[a][1]); f[a][0] = f[a][1] = 0; f[b][0] = 0; f[b][1] = val[b]; dfs(a); now = maxx(now, f[a][0]); ans += now; } printf("%lld\n", ans); return 0;}