洛谷 P2633 王后万岁

王后万岁"/>

洛谷 P2633 王后万岁

题目描述

byteland的王后深受百姓爱戴。为了表达他们的爱，国民们打算占领一个新的国家，并以王后的名字命名。这个国家有n座城市。城市之间有双向道路连接，且每两个城市之间有且仅有一条道路。每座城市对其拥有者来说都有一定的收益。尽管国民们非常爱戴他们的王后，他们并不一定会征服所有的城市献给她。他们只想占领一部分城市（至少有一座），这些城市必须满足两个条件：所有被占领的城市相互间必须是连通的，且城市收益之和最大。你的任务就是算出最大收益是多少。

输入输出格式

输入格式：

第一行是城市的数量n(1<=n<=16000)。第二行包含n个整数，依次表示每座城市的收益，每个数是-1000到1000之间的整数。下面的n-1行描述了道路：每行包含2个整数a和b，用一个空格隔开，表示这两个城市之间有一条道路。

输出格式：

仅有一个数，表示最大收益。

输入输出样例

输入样例#1：

5
-1 1 3 1 -1
4 1
1 3
1 2
4 5

输出样例#1：

4

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

树形DP~

对于每一个点，记f[i]为a[i]，然后遍历，如果子节点f[]大于0，就加上子节点f值，最后输出最大的f值即可~

没有说根节点，但是对于一棵树任意一个节点都可以说是根节点，所以直接从1遍历就可以了~

#include<cstdio>
#include<iostream>
using namespace std;int n,x,y,a[16001],fi[16001],ne[32001],w[32001],cnt,f[16001],fa[16001],maxx;void add(int u,int v)
{w[++cnt]=v;ne[cnt]=fi[u];fi[u]=cnt;
}void findd(int u)
{for(int i=fi[u];i;i=ne[i])if(w[i]!=fa[u]){fa[w[i]]=u;findd(w[i]);if(f[w[i]]>0) f[u]+=f[w[i]];}
}int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=a[i];for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y);add(y,x);}findd(1);for(int i=1;i<=n;i++)if(f[i]>maxx) maxx=f[i];printf("%d\n",maxx);return 0;
}