BZOJ 1040 ZJOI 2008 骑士 树形DP

题意：

有一些战士，他们有战斗力和讨厌的人，选择一些战士，使他们互不讨厌，且战斗力最大，范围1e6

分析：

把战士看作点，讨厌的关系看作一条边，连出来的是一个基环树森林。

对于一棵基环树，我们找出环，选择环上一条边(u,v)。

那么只需考虑两种情况：1、u不选，v任意；2、v不选，u任意。答案取max累计即可

程序：

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 #define REP(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)

 #define mset(a, b) memset(a, b, sizeof(a))

 #define max_(a, b) a > b ? a : b

 const int maxn = 1e6+;

 typedef long long LL;

 int n;

 struct Edge

 {

     int v, nxt;

     Edge (int v = , int nxt = ):

         v(v), nxt(nxt) {}

 }e[maxn*];

 int head[maxn], label;

 int U, V, E, w[maxn];

 bool vis[maxn];

 LL f[maxn][];

 template <class TAT>

 void Ckmax(TAT &a, const TAT &b)

 {

     if (a < b) a = b;

 }

 void ins(int u, int v)

 {

     e[++label] = Edge(v, head[u]), head[u] = label;

     e[++label] = Edge(u, head[v]), head[v] = label;

 }

 void dfs(int u, int fa)

 {

     for (int i = head[u]; i != -; i = e[i].nxt)

     {

         int v = e[i].v;

         if (v == fa) continue ;

         if (vis[v])

         {

             U = u, V = v, E = i;

             continue ;

         }

         vis[v] = true;

         dfs(v, u);

     }

 }

 void work(int u, int fa, int ban)

 {

     f[u][] = , f[u][] = w[u];

     for (int i = head[u]; i != -; i = e[i].nxt)

     {

         int v = e[i].v;

         if (v == fa || i == ban || i == (ban^)) continue ;

         work(v, u, ban);

         f[u][] += max_(f[v][], f[v][]);

         f[u][] += f[v][];

     }

 }

 int main()

 {

     scanf("%d", &n);

     REP(i, , n) head[i] = -;

     label = -;

     REP(i, , n)

     {

         int v;

         scanf("%d %d", &w[i], &v);

         ins(i, v);

     }

     mset(vis, ), mset(f, );

     LL ans = ;

     REP(i, , n)

         if (!vis[i])

         {

             vis[i] = true, dfs(i, );

             LL temp;

             work(U, , E);

             temp = f[U][];

             work(V, , E);

             Ckmax(temp, f[V][]);

             ans += temp;

         }

     printf("%lld\n", ans);

     return ;

 }