#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define pii pair<int, int>
#define f first
#define s second
#define REP(i,n) for (int i = 0; i<n; ++i)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(), (x).end()
#define pb push_back
const int maxn = 2e5+5;
vector<pii> g[maxn];
ll dp[maxn][2][2];
void dfs(int v, int p, ll w) {
vector<pair<ll, ll> > mo0, mo1;
ll sg0 = 0;
ll hmm = 0;
for (pii u : g[v]) {
if (u.f != p) {
dfs(u.f,v,u.s);
mo0.pb({dp[u.f][0][0] - dp[u.f][1][0] + u.s, u.f});
mo1.pb({dp[u.f][0][1] - dp[u.f][1][0] + u.s, u.f});
hmm = max(hmm, dp[u.f][1][1] - dp[u.f][1][0]);
sg0 += dp[u.f][1][0] ;
// sg1 += dp[u.f][1][1] ;
}
}
sort(ALL(mo0), greater<pair<ll, ll> >());
sort(ALL(mo1), greater<pair<ll, ll>>());
dp[v][0][0] = sg0;
dp[v][0][1] = sg0 + hmm;
if (SZ(mo0) >= 2) {
// dp[v][0][1]
if (mo0[0].s != mo1[0].s)
dp[v][0][1] = max(dp[v][0][1], sg0 + mo0[0].f + mo1[0].f);
else
dp[v][0][1] = max(dp[v][0][1], sg0 + max(mo0[0].f + mo1[1].f, mo1[0].f + mo0[1].f));
}
dp[v][1][0] = dp[v][0][0];
dp[v][1][1] = dp[v][0][1];
if (SZ(mo0) >= 1) {
dp[v][1][0] = max(dp[v][1][0], sg0 + mo0[0].f + w);
dp[v][1][1] = max(dp[v][1][1], sg0 + mo1[0].f + w);
dp[v][1][1] = max(dp[v][1][1], dp[v][1][0]);
}
}
signed main(){
IOS();
int n; cin>>n;
// assert(n == 5 || n==10);
// vector<pair<pii, int> > v;
for (int i = 0; i<n-1; ++i) {
int a,b,w; cin>>a>>b>>w;
// if (n == 5 ) assert(a == 1);
--a;--b;
// v.pb({{a,b},w});
g[a].pb({b,w});g[b].pb({a,w});
}
// cout<<re<<endl;
dfs(0,-1,0);
cout<<dp[0][0][1]<<endl;
}
/*
6
1 2 10
1 3 10
1 4 1
4 5 10
4 6 10
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
9 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
9 ms |
4992 KB |
Output is correct |
13 |
Correct |
8 ms |
5120 KB |
Output is correct |
14 |
Correct |
8 ms |
5120 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
17 |
Correct |
8 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
4992 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
9 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
9 ms |
4992 KB |
Output is correct |
13 |
Correct |
8 ms |
5120 KB |
Output is correct |
14 |
Correct |
8 ms |
5120 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
17 |
Correct |
8 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
4992 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
9 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
23 |
Correct |
10 ms |
5504 KB |
Output is correct |
24 |
Correct |
11 ms |
5504 KB |
Output is correct |
25 |
Correct |
10 ms |
5504 KB |
Output is correct |
26 |
Correct |
13 ms |
6016 KB |
Output is correct |
27 |
Correct |
13 ms |
6016 KB |
Output is correct |
28 |
Correct |
13 ms |
6524 KB |
Output is correct |
29 |
Correct |
13 ms |
6400 KB |
Output is correct |
30 |
Correct |
13 ms |
6272 KB |
Output is correct |
31 |
Correct |
14 ms |
6912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
7 ms |
5120 KB |
Output is correct |
3 |
Correct |
7 ms |
4992 KB |
Output is correct |
4 |
Correct |
7 ms |
5120 KB |
Output is correct |
5 |
Correct |
7 ms |
5120 KB |
Output is correct |
6 |
Correct |
7 ms |
5120 KB |
Output is correct |
7 |
Correct |
7 ms |
4992 KB |
Output is correct |
8 |
Correct |
7 ms |
4992 KB |
Output is correct |
9 |
Correct |
7 ms |
4992 KB |
Output is correct |
10 |
Correct |
7 ms |
4992 KB |
Output is correct |
11 |
Correct |
7 ms |
5120 KB |
Output is correct |
12 |
Correct |
9 ms |
4992 KB |
Output is correct |
13 |
Correct |
8 ms |
5120 KB |
Output is correct |
14 |
Correct |
8 ms |
5120 KB |
Output is correct |
15 |
Correct |
7 ms |
4992 KB |
Output is correct |
16 |
Correct |
7 ms |
4992 KB |
Output is correct |
17 |
Correct |
8 ms |
5120 KB |
Output is correct |
18 |
Correct |
7 ms |
4992 KB |
Output is correct |
19 |
Correct |
7 ms |
5120 KB |
Output is correct |
20 |
Correct |
9 ms |
5120 KB |
Output is correct |
21 |
Correct |
7 ms |
4992 KB |
Output is correct |
22 |
Correct |
7 ms |
5120 KB |
Output is correct |
23 |
Correct |
10 ms |
5504 KB |
Output is correct |
24 |
Correct |
11 ms |
5504 KB |
Output is correct |
25 |
Correct |
10 ms |
5504 KB |
Output is correct |
26 |
Correct |
13 ms |
6016 KB |
Output is correct |
27 |
Correct |
13 ms |
6016 KB |
Output is correct |
28 |
Correct |
13 ms |
6524 KB |
Output is correct |
29 |
Correct |
13 ms |
6400 KB |
Output is correct |
30 |
Correct |
13 ms |
6272 KB |
Output is correct |
31 |
Correct |
14 ms |
6912 KB |
Output is correct |
32 |
Correct |
40 ms |
9984 KB |
Output is correct |
33 |
Correct |
41 ms |
9976 KB |
Output is correct |
34 |
Correct |
41 ms |
9976 KB |
Output is correct |
35 |
Correct |
243 ms |
25080 KB |
Output is correct |
36 |
Correct |
221 ms |
25208 KB |
Output is correct |
37 |
Correct |
223 ms |
25080 KB |
Output is correct |
38 |
Correct |
191 ms |
34148 KB |
Output is correct |
39 |
Correct |
186 ms |
30928 KB |
Output is correct |
40 |
Correct |
189 ms |
29220 KB |
Output is correct |
41 |
Correct |
223 ms |
37220 KB |
Output is correct |