HDU 1520 Anniversary party——树形dp

HDU 1520 Anniversary party——树形dp

入门题

#include #include #include #include #include #define IN freopen("in.txt". "r", stdin)#define OUT freopen("out.txt", "w", stdout);using namespace std;const int maxn = 1e4;const int INF = 0x3f3f3f3f;int n, dp[maxn][2], par[maxn];vector g[maxn];void dfs(int root) { for (unsigned int i = 0; i < g[root].size(); i++) { dfs(g[root][i]); } for (unsigned int i = 0; i < g[root].size(); i++) { dp[root][0] += max(dp[g[root][i]][0], dp[g[root][i]][1]); dp[root][1] += dp[g[root][i]][0]; }}int main() { while (~scanf("%d", &n)) { memset(dp, 0, sizeof(dp)); memset(par, -1, sizeof(par)); for (int i = 1; i <= n; i++) { scanf("%d", &dp[i][1]); g[i].clear(); } int u, v; while (~scanf("%d %d", &u, &v) && u && v) { par[u] = v; g[v].push_back(u); } int root = 1; while (par[root] != -1) root = par[root]; dfs(root); printf("%d\n", max(dp[root][1], dp[root][0])); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。