c/c++语言开发共享bozj1040: [ZJOI2008]骑士(奇环树,DP)

题目：

1040: [zjoi2008]骑士

解析：

假设骑士(u)讨厌骑士(v)，我们在(u)，(v)之间连一条边，这样我们就得到了一个奇环树（奇环森林），既然是一颗奇环树，我们就先考虑把环断开，设断开边边连接的两点是(rt1)，(rt2)，断环的话直接标记这条边不能经过就好了

根据题意，我们要求的是相邻两个节点不能同时选时的最大价值，这不就是奇环树版的没有上司的舞会吗。

那么很容易的得到转移方程
设(f[u][1/0])表示以(u)为根，选/不选可以得到的最大价值
[begin{cases} f[u][1] += f[v][0]\\ f[u][0] += max(f[v][0], f[v][1]) end{cases}]

然后分别以(rt1),(rt2)为根做树形dp

因为(rt1)和(rt2)分别是环上的两点，两点不可以同时选，我们分别强制(rt1)，(rt2)不选，累加最大值

原图可能是奇环森林，所以用vis标记一下每个点是否被访问过

代码：

#include <bits/stdc++.h> #define int long long using namespace std; const int n = 2e6 + 10;   int n, m, num = 1, rt1, rt2, flag, ans, kk; int head[n], f[n][2], a[n];   bool vis[n], vis2[n];   struct node {     int v, nx; } e[n];   template<class t>inline void read(t &x) {     x = 0; int f = 0; char ch = getchar();     while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();     while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();     x = f ? -x : x;     return; }   inline void add(int u, int v) {     e[++num] = (node) {v, head[u]}, head[u] = num; }   void findcircle(int u, int fa) {     vis[u] = 1;     for (int i = head[u]; ~i; i = e[i].nx) {         int v = e[i].v;         if (v == fa) continue;         if (!vis[v]) findcircle(v, u);         else {             rt1 = u, rt2 = v;             kk = i;         }     } }   void dfs(int u, int fa) {     f[u][1] = a[u];     for (int i = head[u]; ~i; i = e[i].nx) {         int v = e[i].v;         if (v == fa || i == kk || (i ^ 1) == kk) continue;         dfs(v, u);         f[u][1] += f[v][0];         f[u][0] += max(f[v][1], f[v][0]);     } }   signed main() {     memset(head, -1, sizeof head);     read(n);     for (int i = 1, x; i <= n; ++i) {         read(a[i]), read(x);         add(i, x), add(x, i);     }     for (int i = 1; i <= n; ++i) {         if (vis[i]) continue;         int tmp = 0;         findcircle(i, -1);         memset(f, 0, sizeof f);         dfs(rt1, -1);         tmp = max(tmp, f[rt1][0]);         memset(f, 0, sizeof f);         dfs(rt2, -1);         tmp = max(tmp, f[rt2][0]);         ans += tmp;               }     cout << ans << endl; }