织梦怎么做单页网站,建网站公司营销型网站建设,软件开发公司需要什么硬件设备,家在深圳光明业主论坛题干#xff1a;
在X森林里#xff0c;上帝创建了生命之树。
他给每棵树的每个节点#xff08;叶子也称为一个节点#xff09;上#xff0c;都标了一个整数#xff0c;代表这个点的和谐值。 上帝要在这棵树内选出一个非空节点集S#xff0c;使得对于S中的任意两个点a,…题干
在X森林里上帝创建了生命之树。
他给每棵树的每个节点叶子也称为一个节点上都标了一个整数代表这个点的和谐值。 上帝要在这棵树内选出一个非空节点集S使得对于S中的任意两个点a,b都存在一个点列 {a, v1, v2, ..., vk, b} 使得这个点列中的每个点都是S里面的元素且序列中相邻两个点间有一条边相连。
在这个前提下上帝要使得S中的点所对应的整数的和尽量大。 这个最大的和就是上帝给生命之树的评分。
经过atm的努力他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。
「输入格式」 第一行一个整数 n 表示这棵树有 n 个节点。 第二行 n 个整数依次表示每个节点的评分。 接下来 n-1 行每行 2 个整数 u, v表示存在一条 u 到 v 的边。由于这是一棵树所以是不存在环的。
「输出格式」 输出一行一个数表示上帝给这棵树的分数。
「样例输入」 5 1 -2 -3 4 5 4 2 3 1 1 2 2 5
「样例输出」 8
「数据范围」 对于 30% 的数据n 10 对于 100% 的数据0 n 10^5, 每个节点的评分的绝对值不超过 10^6 。
资源约定 峰值内存消耗 256M CPU消耗 3000ms
解题报告 因为没有试题链接所以就假装AC了。。。写了一遍也没检查可能有错。
不知道是否AC的代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
ll val[MAX];
int n;
vectorint vv[MAX];
ll dp[MAX];
void dfs(int cur,int rt) {int up vv[cur].size();dp[cur] val[cur];for(int i 0; iup; i) {int v vv[cur][i];if(v rt) continue;dfs(v,cur);if(dp[v] 0) dp[cur] dp[v];}
}int main()
{cinn;for(int i 1; in; i) {scanf(%lld,vali);}for(int a,b,i 1; in-1; i) {scanf(%d%d,a,b);vv[a].pb(b);vv[b].pb(a);}dfs(1,-1);ll ans -999999999999;for(int i 1; in; i) {ans max(ans,dp[i]);}cout ans;return 0 ;
}
