当前位置:网站首页>Tree of life (tree DP)
Tree of life (tree DP)
2022-07-06 16:25:00 【AC__ dream】
Data range
1≤n≤10^5,
The absolute value of the score of each node shall not exceed 10^6.
sample input :
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5
sample output :
8
analysis : This question is for us Find the biggest link in the tree , We can Definition f[i] For i Is the value of the largest pass block in the subtree of the root , The result is f[1~n] Maximum of , Tree form DP The process is relatively simple , At first it made f[i]=w[i], That is to make this connected block contain only its own point , Then, as long as the value of the largest pass block in the subtree with the child node as the root is greater than 0, Just add , Follow this dp You can find the answer , Detail reference code :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
#define int long long
const int N=1e5+10;
int w[N*2],f[N],e[N*2],ne[N*2],h[N],idx;//f[i] Said to i Is the maximum value in the connected block of the root
void add(int x,int y)
{
e[idx]=y;
ne[idx]=h[x];
h[x]=idx++;
}
int dp(int x,int father)
{
f[x]=w[x];
for(int i=h[x];i!=-1;i=ne[i])
{
int j=e[i];
if(j==father) continue;
f[x]+=max(dp(j,x),(int)0);
}
return f[x];
}
signed main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]);
memset(h,-1,sizeof h);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%lld%lld",&u,&v);
add(u,v);add(v,u);
}
dp(1,0);
int ans=-0x3f3f3f3f;
for(int i=1;i<=n;i++)
ans=max(ans,f[i]);
printf("%lld",ans);
return 0;
}
边栏推荐
- 树莓派4B安装opencv3.4.0
- 1855. Maximum distance of subscript alignment
- Vs2019 initial use
- Browser print margin, default / borderless, full 1 page A4
- Local visualization tools are connected to redis of Alibaba cloud CentOS server
- Codeforces Round #801 (Div. 2)A~C
- C language must memorize code Encyclopedia
- 921. Minimum additions to make parentheses valid
- (POJ - 3258) River hopper (two points)
- Advancedinstaller installation package custom action open file
猜你喜欢
<li>圆点样式 list-style-type
顺丰科技智慧物流校园技术挑战赛(无t4)
Raspberry pie 4B installation opencv3.4.0
Codeforces Round #802(Div. 2)A~D
Differential (one-dimensional, two-dimensional, three-dimensional) Blue Bridge Cup three body attack
Data storage in memory & loading into memory to make the program run
Advancedinstaller安装包自定义操作打开文件
Borg maze (bfs+ minimum spanning tree) (problem solving report)
2027. Minimum number of operations to convert strings
Installation and configuration of MariaDB
随机推荐
TCP's three handshakes and four waves
双向链表—全部操作
Hdu-6025-prime sequence (girls' competition)
Vs2019 initial use
Installation and use of VMware Tools and open VM tools: solve the problems of incomplete screen and unable to transfer files of virtual machines
Borg maze (bfs+ minimum spanning tree) (problem solving report)
Raspberry pie 4b64 bit system installation miniconda (it took a few days to finally solve it)
Specify the format time, and fill in zero before the month and days
力扣:第81场双周赛
Codeforces Round #803 (Div. 2)A~C
Understand what is a programming language in a popular way
C language learning notes
(POJ - 3186) treatments for the cows (interval DP)
Useeffect, triggered when function components are mounted and unloaded
Pull branch failed, fatal: 'origin/xxx' is not a commit and a branch 'xxx' cannot be created from it
Opencv learning log 28 -- detect the red cup cover
Some problems encountered in installing pytorch in windows11 CONDA
Ball Dropping
SF smart logistics Campus Technology Challenge (no T4)
7-1 understand everything (20 points)