Niuke monthly race 22 tree sub chain

B

The question ：
Just give you a number , Each node has a weight , Now let me ask you what is the maximum sum of the weights of all nodes in a chain .

reflection ：
In fact, this is the method of tree diameter , But this is a point right, not a side right , If it is edge weight, use it twice dfs Or on a tree dp. two dfs It can also find the two endpoints of the tree diameter , But we can't do negative side weight . This problem is on the tree dp That's it .

Code ：

int T,n,m,k;
int maxn = -inf;
int va[N];
int dp[N];

vector<int > e[N];

void dfs(int now,int p)
{
    
	dp[now] = va[now];
	for(auto spot:e[now])
	{
    
		if(spot==p) continue;
		dfs(spot,now);
        maxn = max(maxn,dp[now]+dp[spot]); //now The chain of walking and another chain add up 
		dp[now] = max(dp[now],va[now]+dp[spot]); //now Which chain to follow 
	}
	maxn = max(maxn,dp[now]); // If only one chain 
}

signed main()
{
    
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=1;i<n;i++)
	{
    
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
		e[b].pb(a);
	}
	dfs(1,0);
	cout<<maxn;
	return 0;
}

 Maintain maximum and sub maximum practices ( It is the same as seeking the edge right )：
int T,n,m,k;
int maxn = -inf;
int va[N];
int dp[N][2];

vector<int > e[N];

void dfs(int now,int p)
{
    
	dp[now][0] = dp[now][1] = va[now];
	for(auto spot:e[now])
	{
    
		if(spot==p) continue;
		dfs(spot,now);
		if(dp[now][0]<=dp[spot][0]+va[now])
		{
    
			dp[now][1] = dp[now][0];
			dp[now][0] = dp[spot][0]+va[now];
		}
		else if(dp[spot][0]+va[now]>dp[now][1]) dp[now][1] = dp[spot][0]+va[now];
	}
	maxn = max(maxn,dp[now][0]+dp[now][1]-va[now]); // The subtraction is because the next largest value also selects the current point , To get rid of .
}

signed main()
{
    
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>va[i];
	for(int i=1;i<n;i++)
	{
    
		int a,b;
		cin>>a>>b;
		e[a].pb(b);
		e[b].pb(a);
	}
	dfs(1,0);
	cout<<maxn;
	return 0;
}

 Find the diameter of the tree ( Border right )：

int T,n,m,k;
int maxn;
in
t va[N];
int dp[N][2];

vector<PII > e[N];

void dfs(int now,int p)
{
    
	for(auto t:e[now])
	{
    
		int spot = t.fi,w = t.se;
		if(spot==p) continue;
		dfs(spot,now);
		if(dp[now][0]<dp[spot][0]+w)
		{
    
			dp[now][1] = dp[now][0];
			dp[now][0] = dp[spot][0]+w;
		}
		else if(dp[spot][0]+w>dp[now][1]) dp[now][1] = dp[spot][0]+w;
	}
	maxn = max(maxn,dp[now][0]+dp[now][1]);
}

signed main()
{
    
	IOS;
	cin>>n;
	for(int i=1;i<n;i++)
	{
    
		int a,b,c;
		cin>>a>>b>>c;
		e[a].pb({
    b,c});
		e[b].pb({
    a,c});
	}
	dfs(1,0);
	cout<<maxn;
	return 0;
}

summary ：
Think more , Make up for weaknesses .