原题不抄了
说一个从y总 https://www.acwing.com/activity/content/problem/content/3938/讲的834几相同代码的解
由题干和数据范围可知;
最大的cost形成的方式是从一个没有father的点到另一个没有father的点的路径上的权值和 并抠掉一个端点后的最大值
用y总的方法做树形dp从每个点向上走和向下走,这里和834的代码完全一样,区别仅在于更新的时候需要使用对应的权值(d1[i]和up[i]均不包含i的权值)
两次dfs之后我们依然关注d1和up
用原题样例我打印了跑完的i | d1 | up的结果
0 0 24
1 9 16
2 24 0
3 17 10
4 23 0
5 23 0
我们这里只关注up或者d1有一个为0的点,因为之前说的我们需要端点到端点,因为我们只dfs了两次而且都是从0开始,所以端点就是要不就是0在这个点下面他不能往上走了,要不就是0在这个点上面他不能往下走了
所以我们的答案就是所有d1[i] = 0的up[i]和所有up[i] = 0的d1[i]的集合的最大值
const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n;
int d1[N], d2[N], p1[N], p2[N], up[N];
class Solution {
public:
void add (int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs1(int u, int father, vector<int> & price) {
d1[u] = 0, d2[u] = 0;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == father) continue;
dfs1(j, u, price);
int d = d1[j] + price[j];
if (d > d1[u]) {
d2[u] = d1[u], d1[u] = d;
p2[u] = p1[u], p1[u] = j;
} else if (d > d2[u]) {
d2[u] = d, p2[u] = j;
}
}
}
void dfs2(int u, int father, vector<int> & price) {
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (j == father) continue;
if (j == p1[u]) {
up[j] = max(up[u] , d2[u]) + price[u];
} else {
up[j] = max(up[u], d1[u]) + price[u];
}
dfs2(j, u, price);
}
}
long long maxOutput(int _n, vector<vector<int>>& edges, vector<int>& price) {
n = _n;
memset(h, -1, sizeof(h));
idx = 0;
for (auto e: edges) {
int a = e[0], b = e[1];
add(a, b), add(b, a);
}
dfs1(0, -1, price);
dfs2(0, -1, price);
int ans = 0;
for (int i = 0; i < n; i++) {
cout << i << " " << up[i] << " " << d1[i] << endl;
if (!up[i] || !d1[i]) { // this point starting point or end point;
ans = max(ans, max(up[i], d1[i]));
}
}
return ans;
}
};