[POJ] 1039. Anniversary party

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 1039. Anniversary party
Source            : POJ
Category          : Graph Theory, Dynamic Programing
Algorithm         : DP on Tree
Verdict           : Accepted

#include <iostream>  
#include <vector>  
#include <stdio.h>  
  
using namespace std;  
  
static const int maxn = 6000 + 5;  
  
vector <int> graph[maxn];  
int c[maxn], dp1[maxn], dp2[maxn];  
bool vis[maxn];  
  
inline void dfs(int u, int p)  
{  
    vis[u] = 1;  
    int sum1 = 0, sum2 = 0;  
    for (int v : graph[u])  
    {  
        if (v == p) continue;  
        dfs(v, u);  
        sum1 += dp2[v];  
        sum2 += max(dp1[v], dp2[v]);  
    }  
    dp1[u] = c[u] + sum1;  
    dp2[u] = sum2;  
}  
  
int main()  
{  
    int tnode;  
    scanf("%d", &tnode);  
    for (int i = 1; i <= tnode; i++) scanf("%d", &c[i]);  
    int u, v;  
    while (scanf("%d %d", &u, &v) == 2)  
    {  
        if (u + v == 0) break;  
        graph[u].push_back(v);  
        graph[v].push_back(u);  
    }  
    int ans = 0;  
    for (int i = 1; i <= tnode; i++)  
    {  
        if (!vis[i])  
        {  
            dfs(i, -1);  
            ans += max(dp1[i], dp2[i]);  
        }  
    }  
    printf("%d\n", ans);  
}