hdu1520

基本的树形dp

#include <cstring>
#include <cstdio>
#include <vector>
using namespace std; const int MAX_N = (int)(6e3) + ; int n;
int weight[MAX_N];
vector <int> edge[MAX_N];
bool vis[MAX_N];
int dp[MAX_N][];
int root; void dfs(int father, int u)
{
for (int i = ; i < (int)edge[u].size(); i++)
{
int v = edge[u][i];
if (v != father)
dfs(u, v);
}
dp[u][] = ;
dp[u][] = weight[u];
for (int i = ; i < (int)edge[u].size(); i++)
{
int v = edge[u][i];
if (v == father)
continue;
dp[u][] += max(dp[v][], dp[v][]);
dp[u][] += dp[v][];
}
} void input()
{
for (int i = ; i < n; i++)
{
scanf("%d", &weight[i]);
edge[i].clear();
}
memset(vis, , sizeof(vis));
int a, b;
while (scanf("%d%d", &a, &b), a | b)
{
a--;
b--;
vis[a] = true;
edge[a].push_back(b);
edge[b].push_back(a);
}
for (int i = ; i < n; i++)
{
if (!vis[i])
{
root = i;
break;
}
}
} int main()
{
while (scanf("%d", &n) != EOF)
{
input();
dfs(-, root);
printf("%d\n", max(dp[root][], dp[root][]));
}
return ;
}
上一篇:linux grep命令(linux在文件中搜索内容)


下一篇:第13月第25天 ios11 uitableview reloaddata contentsize