This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, int> ii;
const int N = 2e5 + 10;
vector<int> adj[N], cost[N];
ll S[N], M[N], ans;
int n, pcost[N];
void calc(int u, int par) {
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(v == par) continue;
pcost[v] = c; calc(v, u);
S[u] += max(S[v], M[v]);
}
for(int v : adj[u]) if(v - par) {
M[u] = max(M[u], S[u] - max(S[v], M[v]) + S[v] + pcost[u] + pcost[v]);
}
}
void solve(int u, int par) {
ans = max(ans, S[u]);
vector<ii> l = {{-1e18, 0}};
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(v == par) continue;
l.push_back({-max(S[v], M[v]) + S[v] + c, v});
} sort(l.begin(), l.end(), greater<ii>());
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(v == par) continue;
ll a = S[u], b = S[v], C = M[u], d = M[v];
S[u] -= max(S[v], M[v]);
M[u] = S[u] + c + (l[0].second == v ? l[1].first : l[0].first);
S[v] += max(S[u], M[u]);
solve(v, u);
S[u] = a, S[v] = b, M[u] = C, M[v] = d;
}
}
int main() {
int n; scanf("%d", &n);
for(int i = 1; i < n; i++) {
int u, v, c;
scanf("%d %d %d", &u, &v, &c);
adj[u].push_back(v);
adj[v].push_back(u);
cost[u].push_back(c);
cost[v].push_back(c);
}
calc(1, 0);
solve(1, 0);
printf("%lld\n", ans);
}
Compilation message (stderr)
beads.cpp: In function 'void calc(int, int)':
beads.cpp:13:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
beads.cpp: In function 'void solve(int, int)':
beads.cpp:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
beads.cpp:32:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:45:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n; scanf("%d", &n);
~~~~~^~~~~~~~~~
beads.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |