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;
void dfs(long long x, long long p, vector<long long> &wire, vector<long long> &nowire, vector<vector<pair<long long, long long>>> &AR, vector<long long> &up)
{
long long sum = 0, best1 = -1234567890, best2 = -1234567890;
for (long long i = 0; i < AR[x].size(); i++)
{
if (AR[x][i].first == p)
{
up[x] = AR[x][i].second;
continue;
}
dfs(AR[x][i].first, x, wire, nowire, AR, up);
sum += wire[AR[x][i].first];
long long temp = nowire[AR[x][i].first] - wire[AR[x][i].first] + up[AR[x][i].first];
if (temp > best1)
swap(best1, temp);
if (temp > best2)
swap(best2, temp);
}
if (AR[x].size() > 2)
nowire[x] = sum + best1 + best2;
if (AR[x].size() > 1 && x != 0)
wire[x] = sum + best1 + up[x];
wire[x] = max(wire[x], nowire[x]);
}
int main()
{
long long N;
cin >> N;
vector<vector<pair<long long, long long>>> AR(N);
for (long long i = 0; i < N - 1; i++)
{
long long a, b, c;
cin >> a >> b >> c;
a--, b--;
AR[a].push_back({b, c});
AR[b].push_back({a, c});
}
vector<long long> wire(N), nowire(N), up(N);
dfs(0, 0, wire, nowire, AR, up);
cout << wire[0];
}
Compilation message (stderr)
beads.cpp: In function 'void dfs(long long int, long long int, std::vector<long long int>&, std::vector<long long int>&, std::vector<std::vector<std::pair<long long int, long long int> > >&, std::vector<long long int>&)':
beads.cpp:6:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
6 | for (long long i = 0; i < AR[x].size(); i++)
| ~~^~~~~~~~~~~~~~
# | 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... |