//In the name of God
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
ll n, dp[maxn][2], pd[maxn][2], par[maxn];
vector<pll> g[maxn];
bool vis[maxn];
void dfs(ll v){
ll mx = -inf;
vis[v] = 1;
for(pll u : g[v]){
if(vis[u.F]) continue;
dfs(u.F);
par[u.F] = u.S;
dp[v][0] += max(dp[u.F][0], dp[u.F][1] + u.S);
mx = max(mx, dp[u.F][0] + u.S - max(dp[u.F][0], dp[u.F][1] + u.S));
}
dp[v][1] = dp[v][0] + mx;
}
void sfd(ll v, ll p = -1){
vis[v] = 1;
ll s = 0;
if(~p) s += max(pd[v][0], pd[v][1] + p);
vector<pll> vec;
if(~p) vec.pb(Mp(pd[v][0] + p - max(pd[v][0], pd[v][1] + p), v));
for(pll u : g[v]){
if(vis[u.F]) continue;
s += max(dp[u.F][0], dp[u.F][1] + u.S);
vec.pb(Mp(dp[u.F][0] + u.S - max(dp[u.F][0], dp[u.F][1] + u.S), u.F));
}
sort(all(vec), greater<pll>());
vec.pb(Mp(-inf, 0));
for(pll u : g[v]){
if(vis[u.F]) continue;
pd[u.F][0] = s - max(dp[u.F][0], dp[u.F][1] + u.S);
pd[u.F][1] = pd[u.F][0] + (vec[0].S == u.F ? vec[1].F : vec[0].F);
sfd(u.F, u.S);
}
return;
}
int main(){
fast_io;
cin >> n;
for(ll i = 1; i < n; i++){
ll v, u, c;
cin >> v >> u >> c;
g[v].pb(Mp(u, c));
g[u].pb(Mp(v, c));
}
dfs(4);
fill(vis, vis + n + 1, 0);
sfd(4);
ll ans = 0;
for(ll i = 1; i <= n; i++){
ans = max(ans, dp[i][0] + max(pd[i][0], pd[i][1] + par[i]));
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5072 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
5032 KB |
Output is correct |
5 |
Correct |
3 ms |
4976 KB |
Output is correct |
6 |
Correct |
3 ms |
5020 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5008 KB |
Output is correct |
9 |
Correct |
3 ms |
5024 KB |
Output is correct |
10 |
Correct |
3 ms |
5012 KB |
Output is correct |
11 |
Correct |
3 ms |
5060 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5072 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
5032 KB |
Output is correct |
5 |
Correct |
3 ms |
4976 KB |
Output is correct |
6 |
Correct |
3 ms |
5020 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5008 KB |
Output is correct |
9 |
Correct |
3 ms |
5024 KB |
Output is correct |
10 |
Correct |
3 ms |
5012 KB |
Output is correct |
11 |
Correct |
3 ms |
5060 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
5032 KB |
Output is correct |
15 |
Correct |
3 ms |
5028 KB |
Output is correct |
16 |
Correct |
3 ms |
5032 KB |
Output is correct |
17 |
Correct |
3 ms |
5068 KB |
Output is correct |
18 |
Correct |
4 ms |
5064 KB |
Output is correct |
19 |
Correct |
4 ms |
5068 KB |
Output is correct |
20 |
Correct |
3 ms |
5068 KB |
Output is correct |
21 |
Correct |
3 ms |
5068 KB |
Output is correct |
22 |
Correct |
3 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5072 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
5032 KB |
Output is correct |
5 |
Correct |
3 ms |
4976 KB |
Output is correct |
6 |
Correct |
3 ms |
5020 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5008 KB |
Output is correct |
9 |
Correct |
3 ms |
5024 KB |
Output is correct |
10 |
Correct |
3 ms |
5012 KB |
Output is correct |
11 |
Correct |
3 ms |
5060 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
5032 KB |
Output is correct |
15 |
Correct |
3 ms |
5028 KB |
Output is correct |
16 |
Correct |
3 ms |
5032 KB |
Output is correct |
17 |
Correct |
3 ms |
5068 KB |
Output is correct |
18 |
Correct |
4 ms |
5064 KB |
Output is correct |
19 |
Correct |
4 ms |
5068 KB |
Output is correct |
20 |
Correct |
3 ms |
5068 KB |
Output is correct |
21 |
Correct |
3 ms |
5068 KB |
Output is correct |
22 |
Correct |
3 ms |
5068 KB |
Output is correct |
23 |
Correct |
6 ms |
5580 KB |
Output is correct |
24 |
Correct |
6 ms |
5584 KB |
Output is correct |
25 |
Correct |
6 ms |
5452 KB |
Output is correct |
26 |
Correct |
9 ms |
6092 KB |
Output is correct |
27 |
Correct |
10 ms |
6072 KB |
Output is correct |
28 |
Correct |
10 ms |
6312 KB |
Output is correct |
29 |
Correct |
10 ms |
6268 KB |
Output is correct |
30 |
Correct |
10 ms |
6224 KB |
Output is correct |
31 |
Correct |
11 ms |
6584 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5072 KB |
Output is correct |
2 |
Correct |
3 ms |
4940 KB |
Output is correct |
3 |
Correct |
3 ms |
4940 KB |
Output is correct |
4 |
Correct |
3 ms |
5032 KB |
Output is correct |
5 |
Correct |
3 ms |
4976 KB |
Output is correct |
6 |
Correct |
3 ms |
5020 KB |
Output is correct |
7 |
Correct |
4 ms |
5032 KB |
Output is correct |
8 |
Correct |
3 ms |
5008 KB |
Output is correct |
9 |
Correct |
3 ms |
5024 KB |
Output is correct |
10 |
Correct |
3 ms |
5012 KB |
Output is correct |
11 |
Correct |
3 ms |
5060 KB |
Output is correct |
12 |
Correct |
3 ms |
4940 KB |
Output is correct |
13 |
Correct |
3 ms |
4940 KB |
Output is correct |
14 |
Correct |
3 ms |
5032 KB |
Output is correct |
15 |
Correct |
3 ms |
5028 KB |
Output is correct |
16 |
Correct |
3 ms |
5032 KB |
Output is correct |
17 |
Correct |
3 ms |
5068 KB |
Output is correct |
18 |
Correct |
4 ms |
5064 KB |
Output is correct |
19 |
Correct |
4 ms |
5068 KB |
Output is correct |
20 |
Correct |
3 ms |
5068 KB |
Output is correct |
21 |
Correct |
3 ms |
5068 KB |
Output is correct |
22 |
Correct |
3 ms |
5068 KB |
Output is correct |
23 |
Correct |
6 ms |
5580 KB |
Output is correct |
24 |
Correct |
6 ms |
5584 KB |
Output is correct |
25 |
Correct |
6 ms |
5452 KB |
Output is correct |
26 |
Correct |
9 ms |
6092 KB |
Output is correct |
27 |
Correct |
10 ms |
6072 KB |
Output is correct |
28 |
Correct |
10 ms |
6312 KB |
Output is correct |
29 |
Correct |
10 ms |
6268 KB |
Output is correct |
30 |
Correct |
10 ms |
6224 KB |
Output is correct |
31 |
Correct |
11 ms |
6584 KB |
Output is correct |
32 |
Correct |
51 ms |
10308 KB |
Output is correct |
33 |
Correct |
64 ms |
10296 KB |
Output is correct |
34 |
Correct |
65 ms |
10476 KB |
Output is correct |
35 |
Correct |
367 ms |
26768 KB |
Output is correct |
36 |
Correct |
354 ms |
26888 KB |
Output is correct |
37 |
Correct |
321 ms |
26912 KB |
Output is correct |
38 |
Correct |
243 ms |
29116 KB |
Output is correct |
39 |
Correct |
225 ms |
31080 KB |
Output is correct |
40 |
Correct |
261 ms |
29488 KB |
Output is correct |
41 |
Correct |
345 ms |
36852 KB |
Output is correct |