#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class A> ostream& operator<<(ostream &cout, vector<A> const &v) {cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";};
template<class A, class B> ostream& operator<<(ostream &cout, const pair<A,B> &x) {return cout << "(" <<x.first << ", " << x.second << ")";};
template <class T> void pv(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) cerr << *i << " "; cerr << "]\n";}
void _print() {cerr << "]\n";}
template <class T, class... V> void _print(T t, V... v) {cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#define fi first
#define se second
#define SZ(x) (int)((x).size())
#define pii pair<ll,ll>
const int mx = 2e5+5;
vector<pii> adj[mx];
int n;
ll dp[mx][2]; //free to put whatever, need to connect parent
void dfs (int v, int p) {
ll base = 0;
vector<ll> boost;
for (pii x : adj[v]) {
ll a = x.fi, b = x.se;
if (a == p) continue;
dfs(a,v);
if (dp[a][0] == -1) {
if (dp[a][1] != -1) base += b+dp[a][1];
} else if (dp[a][1] == -1) {
base += dp[a][0];
boost.push_back(b);
} else {
ll z = max(dp[a][0], dp[a][1]+b);
base += z;
boost.push_back(dp[a][0]+b-z);
}
}
sort(boost.rbegin(), boost.rend());
dp[v][0] = base;
if (SZ(boost) >= 2) dp[v][0] = max(dp[v][0], base+boost[0]+boost[1]);
if (SZ(boost) >= 1) dp[v][1] = base+boost[0];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int q = 0; q < n-1; q++) {
ll a,b,c;
cin >> a >> b >> c;
adj[a].emplace_back(b,c);
adj[b].emplace_back(a,c);
}
for (int q = 0; q < mx; q++) for (int w = 0; w < 2; w++) dp[q][w] = -1;
dfs(1,0);
cout << dp[1][0] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 5 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 5 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 5 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 2 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 3 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 4 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 5 |
Correct |
6 ms |
8172 KB |
Output is correct |
| 6 |
Incorrect |
6 ms |
8172 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
