洛谷_P2633王后万岁

正文索引 [隐藏]

题目描述

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

输入格式:

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

输出格式:

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

输入样例

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

输出样例:

4

题解

好久不写OI题了。。今天有幸写了一题水树形DP。。。恩,一遍A感觉蛮好的233![虽然好像要被裱...
从下往上更新最大贡献就行,每个节点记得更新答案,就好。一遍O(n)的!

<

pre class=”lang:c++ decode:true “>
[code lang=”cpp”]
#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=16010;
const int Inf=Maxn1000;
struct Edge{
int v,nxt;
Edge(){}
Edge(int v0,int n0){
v=v0;
nxt=n0;
}
};
Edge e[Maxn
2+5];
int head[Maxn];
int nume;
inline void addEdge(int u,int v){
e[++nume]=Edge(u,head[v]);
head[v]=nume;
e[++nume]=Edge(v,head[u]);
head[u]=nume;
}
int val[Maxn];
int ans[Maxn];
int Ans;
int n;
void dfs(int x,int fa){
ans[x]=val[x];
for (int i=head[x];i;i=e[i].nxt){
int v=e[i].v;
if (v!=fa){
dfs(v,x);
if (ans[v]>0) ans[x]+=ans[v];
}
}
if (ans[x]>0) Ans=max(Ans,ans[x]);
//printf("#:%d Ans:%d\n",x,ans[x]);
}
int main(){
scanf("%d",&n);
Ans=-Inf;
for (int i=1;i<=n;i++) scanf("%d",&val[i]);
for (int i=1;i<=n;i++) Ans=max(Ans,val[i]);
for (int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
addEdge(x,y);
}
dfs(1,0);
printf("%d\n",Ans);
return 0;
}</pre>
[/code]