题目链接
题目描述：
有一棵 n (1 < n < 1e6) 个结点的树，每个点和每条边都存在一个价值 (-500 ≤ w ≤ 500)。对于树上点对的价值，包括点对的起点和终点以及路径上边权值之和，不包括路径上其他点值。求这颗树上最大的点对价值为多少。点对至少需要两个点。
题解：
我们发现如果维护带两个端点的链比较麻烦，所以我们可以考虑维护只有一个端点的链，我们先考虑根节点，经过根节点的最长链就是从根节点的子树中选择带一个端点的最长的两条链进行相连，对于其他节点 x，如果最长链经过根节点，这种情况已经在上面包含了，如果不经过根节点而经过节点 x，那么经过 x 的最长链就是从 x 的子树中选择最长的两条带一个端点的链进行相连，然后继续这个过程。 设 dp[i] 表示以 i 为根的树的结点到达 i 的最大值(包括一个端点的权值和经过的路径权值和)，在更新答案时，
a
n
s
=
m
a
x
(
a
n
s
,
d
p
[
x
]
+
d
p
[
y
]
+
z
)
ans = max(ans, dp[x] + dp[y] + z)
ans=max(ans,dp[x]+dp[y]+z)，dp[x]代表上个子结点k最优，dp[y]是当前以 y 为根的子树中最优值，将这两个链连接起来的值就等于
d
p
[
x
]
,
d
p
[
y
]
+
z
dp[x], dp[y] + z
dp[x],dp[y]+z，然后更新 dp[x]，状态转移方程为
d
p
[
x
]
=
m
a
x
(
d
p
[
x
]
,
d
p
[
y
]
+
z
)
dp[x] = max(dp[x], dp[y] + z)
dp[x]=max(dp[x],dp[y]+z)。
AC Codes：
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std
;
typedef long long ll
;
const int N
= 1e6 + 6, M
= 1e9 + 7, INF
= 0x3f3f3f3f;
int dp
[N
], c
[N
], ans
;
int head
[N
], Next
[N
<< 1], ver
[N
<< 1], edge
[N
<< 1], tot
;
void add(int u
, int v
, int w
) {
ver
[++tot
] = v
, edge
[tot
] = w
;
Next
[tot
] = head
[u
], head
[u
] = tot
;
}
void dfs(int x
, int fa
) {
dp
[x
] = c
[x
];
for (int i
= head
[x
]; i
; i
= Next
[i
]) {
int y
= ver
[i
], z
= edge
[i
];
if (y
== fa
) continue;
dfs(y
, x
);
ans
= max(ans
, dp
[x
] + dp
[y
] + z
);
dp
[x
] = max(dp
[x
], dp
[y
] + z
);
}
}
int main() {
ios
::sync_with_stdio(false);
cin
.tie(0), cout
.tie(0);
int T
;
cin
>> T
;
while (T
--) {
int n
;
cin
>> n
;
tot
= 1;
for (int i
= 1; i
<= n
; i
++) head
[i
] = 0, dp
[i
] = 0;
for (int i
= 2; i
<= n
; i
++) {
int y
, z
;
cin
>> y
>> z
;
add(i
, y
, z
), add(y
, i
, z
);
}
for (int i
= 1; i
<= n
; i
++) cin
>> c
[i
];
ans
= -2e9;
dfs(1, -1);
cout
<< ans
<< '\n';
}
return 0;
}
