HDU 1520Anniversary party（树型DP）

时间：2023-01-27 20:22:10

HDU 1520   Anniversary party

题目是说有N个人参加party，每个人有一个rating值（可以理解为权值）和一个up（上司的编号），为了保证party的趣味性，每一个人不可以和他的直接上司都参加，问最后的rating和最大

这是一个典型的树形DP,DP[i][0]表示i不参加那他的这棵子树上的最大权值，DP[i][1]表示i参加时的这棵树上的最大权值，那么：

　　　　　　　　DP[i][0] = sum{MAX(DP[j][1]， DP[j][0])  |  j是i的直接子节点}

　　　　　　　　DP[i][1] = sum{DP[j][0]  |  j是i的直接子节点}　　　　　　　　

 //#pragma comment(linker,"/STACK:102400000,102400000")

 #include <map>

 #include <set>

 #include <stack>

 #include <queue>

 #include <cmath>

 #include <ctime>

 #include <vector>

 #include <cstdio>

 #include <cctype>

 #include <cstring>

 #include <cstdlib>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 #define INF 1e9

 #define inf (-((LL)1<<40))

 #define lson k<<1, L, mid

 #define rson k<<1|1, mid+1, R

 #define mem0(a) memset(a,0,sizeof(a))

 #define mem1(a) memset(a,-1,sizeof(a))

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

 #define FOPENIN(IN) freopen(IN, "r", stdin)

 #define FOPENOUT(OUT) freopen(OUT, "w", stdout)

 template<class T> T CMP_MIN(T a, T b) { return a < b; }

 template<class T> T CMP_MAX(T a, T b) { return a > b; }

 template<class T> T MAX(T a, T b) { return a > b ? a : b; }

 template<class T> T MIN(T a, T b) { return a < b ? a : b; }

 template<class T> T GCD(T a, T b) { return b ? GCD(b, a%b) : a; }

 template<class T> T LCM(T a, T b) { return a / GCD(a,b) * b;    }

 //typedef __int64 LL;

 //typedef long long LL;

 const int MAXN = ;

 const int MAXM = ;

 const double eps = 1e-;

 //const LL MOD = 1000000007;

 int N, a[MAXN], dp[MAXN][];

 int fa[MAXN];

 vector<int>e[MAXN];

 void DFS(int u)

 {

     int s0 = , s1 = ;

     for(int i=;i<e[u].size();i++)

     {

         DFS(e[u][i]);

         s0 += MAX( dp[e[u][i]][], dp[e[u][i]][] );

         s1 += dp[e[u][i]][];

     }

     dp[u][] = s0;

     dp[u][] = s1 + a[u];

 }

 int main()

 {

     //FOPENIN("in.txt");

     while(~scanf("%d", &N))

     {

         mem0(dp);

         for(int i=;i<=N;i++)

         {

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

             fa[i] = i;

             e[i].clear();

         }

         int x, y;

         while(scanf("%d %d", &x, &y) && (x||y) ){

             e[y].push_back(x);

             fa[x] = y;

         }

         int ans = ;

         for(int i=;i<=N;i++) if(fa[i] == i)

         {

             DFS(i);

             ans += MAX(dp[i][], dp[i][]);

         }

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

     }

     return ;

 }

相关文章