题目描述

给定一棵树 T ，树 T 上每个点都有一个权值。

定义一颗树的子链的大小为：这个子链上所有结点的权值和 。

请在树 T 中找出一条最大的子链并输出。

输入描述:

第一行输入一个 n,1≤n≤105。

接下来一行包含n个数，对于每个数 ai,−10^5≤ai≤10^5，表示 i 结点的权值。

接下来有n-1行，每一行包含两个数u，v（ 1≤u,v≤n , u != v），表示u与v之间有一条边。

输出描述:

仅包含一个数，表示我们所需要的答案。

示例1

输入

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

输出

4

说明

样例中最大子链为1 -> 2 -> 5

备注:

一个结点，也可以称作一条链

 树形dp：

如果值在边上的话

void DP(int u,int pa)
{dp[u]=0;for(int i=h[u];i;i=ne[i]){int v=e[i];if(v==pa) continue;DP(v,u);ans=max(ans,dp[u]+dp[v]+dis[i]);dp[u]=max(dp[u],dp[v]+dis[i]);}
}

如果值在点上的话

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF =0x3f3f3f3f;
const int N=1e5+10;
int n;
ll idx,e[N*2],h[N],ne[2*N],w[N],dp[N],ans;
bool vis[N];
void add(int x,int y)
{e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}
void dfs(int x)
{dp[x]=w[x];vis[x]=1;ans=max(ans,w[x]);for(int i=h[x]; ~i; i=ne[i]){int j=e[i];if(vis[j])continue;dfs(j);ans=max(ans,dp[x]+dp[j]);dp[x]=max(dp[x],dp[j]+w[x]);}
}
int  main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;memset(h,-1,sizeof h);ans=-INF;for(int i=1; i<=n; i++){cin>>w[i];}for(int i=1; i<=n-1; i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}dfs(1);cout<<ans;return 0;
}

两次dfs

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF =0x3f3f3f3f;
const int N=1e5+10;
int n,pos;
ll idx,e[N*2],h[N],ne[2*N],w[N],dp[N],ans;
bool vis[N];
void add(int x,int y)
{e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}
void dfs(int now,ll x)
{vis[now]=1;if(ans<x){ans=x;pos=now;}for(int i=h[now]; ~i; i=ne[i]){int j=e[i];if(vis[j])continue;dfs(j,x+w[j]);}
}
int  main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;memset(h,-1,sizeof h);ans=-INF;for(int i=1; i<=n; i++){cin>>w[i];}for(int i=1; i<=n-1; i++){int u,v;cin>>u>>v;add(u,v);add(v,u);}dfs(1,w[1]);//cout<<ans;memset(vis,0,sizeof vis);dfs(pos,w[pos]);cout<<ans;return 0;
}