牛客小白月赛22—B-树上子链
链接：https://ac.nowcoder.com/acm/contest/4462/B
来源：牛客网
给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。
输入描述:
第一行输入一个 n,1≤n≤105n,1 \le n \le 10^5n,1≤n≤105。
接下来一行包含n个数，对于每个数 ai,−105≤ai≤105a_i, -10^5 \le a_i \le 10^5ai,−105≤ai≤105，表示 i 结点的权值。
接下来有n-1行，每一行包含两个数u，v（ 1≤u,v≤n1 \le u,v \le n1≤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[i]代表从iii结点到以其为根的子树中任意一个点的路径最大值
val[i]为i节点的点权，child[i][j]为i节点的第j个儿子的编号
则动态转移方程为 dp[i]=max(dp[child[i][j]]+val[i],f[i],val[i])
另外要有一个更新ans的代码ans=max(ans,dp[u]+dp[x]);
这条语句一定要放在更新dp[u]之前，因为dp[u]+dp[x]是当前根的左子树或者右子树的长度的最大值，如果更新完dp[u]，那么dp[u]就代表着左子树加上右子树的最大值了
#include
using namespace std;
typedef long long ll;
vector v[100005];
ll a[100005],dp[100005],ans=-0x3f3f3f3f;
ll maxx=-0x3f3f3f3f;
void dfs(ll u,ll f)
{
dp[u]=a[u];
for(int i=0;i>n;
for(int i=1;i>a[i];
for(int i=1;i>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
cout <<ans<<endl;
}
作者：lywyqmam
