题目
题目描述
给定一棵树 T ，树 T 上每个点都有一个权值。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。
输入描述
第一行输入一个 \(n,1 \le n \le 10^5\) 。
接下来一行包含n个数，对于每个数 \(a_i, -10^5 \le a_i \le 10^5\) ，表示 i 结点的权值。
接下来有n-1行，每一行包含两个数u，v（ \(1 \le u,v \le 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。
这道题是树的直径的变种题，树上权值最大链。
考虑以 \(1\) 为根，设 \(dp[u]\) 为以 \(u\) 为根的子树中过 \(u\) 的最大单链（指只沿着 \(u\) 的一个子结点方向扩展，而不是分成两个子节点）。转移方程为：\(dp[u] = \max(dp[u],dp[v_i]+a[u])\)。
一颗子树 \(u\) 的最大直径，可以通过其子节点的子树 \(v_i\) 的最大直径的最大值，以及过自己点形成的链的最大值得到。而后者通过过 \(u\) 的最长链加次长链得到。对于前者，我们只要求最大的即可，所以可以通过 \(ans\) 记录目前为止最大直径，即可满足前者要求。后者的最长链加次长链有两种方法：
- 记录一次遍历子节点中的最长链 \(d_1\) 和次长链 \(d_2\) ，最后 \(\max (ans,d_1+d_2)\) 即可。
- 可以通过在求 \(dp[u]\) 的过程中得到，而不用两个变量记录。首先 \(dp[u]\) 一定会经过最长链并且记录它，其次在其他情况必定会经过次长链，因此可以通过 \(\max (ans,dp[u] + dp[v])\) 来表示目前为止过 \(u\) 的最长链加上当前子节点的最长链的和。如果最长链在次长链之前，则显然可以；如果之后，则在遇到最长链之前一定是次长链最长，最后一定会得到次长链加最长链的情况，所以这种方法可行。需要注意的是，这步操作要在这次求 \(dp[u]\) 之前完成，因为 \(dp[u]\) 的更新包括了 \(dp[v]\)，如果放在这之后，会有可能加两次 \(dp[v]\) ，然而这是不合法的。
个人觉得第二种求的方式比较方便。
扩展1：根节点确定，求树中各个子树的直径，只需要每次遍历子节点之后把最终ans记录下就行。
扩展2：求树中过每个子节点的最长链，这个需要求最长单链时记录最长单链和次长单链以及对应的节点，因为有可能该节点就在父节点的最长单链上，需要和父节点的次长单链结合，总体就是换根dp一下。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
方法一
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> g[100007];
int a[100007];
ll dp[100007];///以u向下的单链最大权值
ll ans = -1e18;///初始化负无穷
///如果求任意子树的直径，要在这个基础上再加个f[u],表示以u为根的子树的最大直径
///从f[v],d1+d2+a[u]转移，表示子树的最大直径和过u的直径取最大值
int dfs(int u, int fa) {
ll d1 = 0, d2 = 0;///子最长，子次长，因为可以不选所以初始为0
dp[u] = a[u];///初始化
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u] = max(dp[u], a[u] + dp[v]);///更新过u单链最大权值
if (dp[v] > d1) d2 = d1, d1 = dp[v];
else if (dp[v] > d2) d2 = dp[v];
}
ans = max(ans, d1 + d2 + a[u]);
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i < n;i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, 0);
cout << ans << '\n';
return 0;
}
方法二
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> g[100007];
int a[100007];
ll dp[100007];///以u向下的单链最大权值
ll dfs(int u, int fa) {
dp[u] = a[u];///过u初始化
ll ans = a[u];///初始化单点，防止无孩子
for (auto v : g[u]) {
if (v == fa) continue;
ans = max(ans, dfs(v, u));///子树最大值（不一定过子节点）
ans = max(ans, dp[u] + dp[v]);///尝试过u最大值 = u最长单链（u+子最长子链） + 子次长子链
dp[u] = max(dp[u], a[u] + dp[v]);///更新过u单链最大权值，要在答案更新下面，不然会加两次同样的值
}
return ans;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i < n;i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
cout << dfs(1, 0) << '\n';
return 0;
}