Tree of life (tree DP)

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;
}