#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 200020
int n, dp[maxn][2], ans;
pair<int,int> mxv[maxn];
vector<pair<int,int>> g[maxn];
// dp(u,1) ta com azul pro pai e vai ter qual o melhor pra continuar assim
//
void dfs(int u, int p) {
int ans1 = 0;
mxv[u] = mp(-inf,-inf);
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(v == p) continue;
dfs(v,u);
ans1+= max(dp[v][0],dp[v][1]+w);
mxv[u].sc = max(mxv[u].sc, dp[v][0] + w - max(dp[v][0],dp[v][1]+w));
if(mxv[u].sc > mxv[u].fr) swap(mxv[u].fr,mxv[u].sc);
}
dp[u][0] = ans1;
dp[u][1] = ans1+mxv[u].fr;
// cout << u << " -- " << dp[u][0] << " " << dp[u][1] << endl;
}
void reroot(int u, int p, int wp) {
//p é a raiz da tree até entao
//tiro o u do p e insiro o p no u
int antu0 = dp[u][0];
int antu1 = dp[u][1];
int antp0 = dp[p][0];
int antp1 = dp[p][1];
pair<int,int> antmxv = mxv[u];
//tirar u do p
dp[p][0]-= max(dp[u][0],dp[u][1]+wp);
if(mxv[p].fr == dp[u][0] + wp - max(dp[u][0],dp[u][1]+wp)) dp[p][1] = dp[p][0]+mxv[p].sc;
else dp[p][1] = dp[p][0] + mxv[p].fr;
//insiro p em u
dp[u][0]+= max(dp[p][0],dp[p][1]+wp);
mxv[u].sc = max(mxv[u].sc, dp[p][0] + wp - max(dp[p][0],dp[p][1]+wp));
if(mxv[u].sc > mxv[u].fr) swap(mxv[u].fr,mxv[u].sc);
dp[u][1] = dp[u][0] + mxv[u].fr;
ans = max(ans, dp[u][0]);
for(auto V : g[u]) {
int v = V.fr;
int w = V.sc;
if(v == p) continue;
reroot(v,u,w);
}
//volta as respostas anteriores
dp[u][0] = antu0;
dp[u][1] = antu1;
dp[p][0] = antp0;
dp[p][1] = antp1;
mxv[u] = antmxv;
}
void solve() {
cin >> n;
for(int i = 1; i < n; i++) {
int u,v,w; cin >> u >> v >> w;
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
}
dfs(1,1);
ans = dp[1][0];
for(auto V : g[1]) {
int v = V.fr;
int w = V.sc;
reroot(v,1,w);
}
cout << ans << endl;
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5024 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5024 KB |
Output is correct |
9 |
Correct |
2 ms |
5024 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
5024 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5024 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5024 KB |
Output is correct |
9 |
Correct |
2 ms |
5024 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
5024 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
5028 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
5024 KB |
Output is correct |
18 |
Correct |
3 ms |
5024 KB |
Output is correct |
19 |
Correct |
4 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5024 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5024 KB |
Output is correct |
9 |
Correct |
2 ms |
5024 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
5024 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
5028 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
5024 KB |
Output is correct |
18 |
Correct |
3 ms |
5024 KB |
Output is correct |
19 |
Correct |
4 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5032 KB |
Output is correct |
23 |
Correct |
5 ms |
5428 KB |
Output is correct |
24 |
Correct |
6 ms |
5420 KB |
Output is correct |
25 |
Correct |
6 ms |
5420 KB |
Output is correct |
26 |
Correct |
10 ms |
5936 KB |
Output is correct |
27 |
Correct |
10 ms |
5932 KB |
Output is correct |
28 |
Correct |
7 ms |
5968 KB |
Output is correct |
29 |
Correct |
8 ms |
5940 KB |
Output is correct |
30 |
Correct |
7 ms |
5936 KB |
Output is correct |
31 |
Correct |
7 ms |
6316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
3 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
5024 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
3 ms |
5024 KB |
Output is correct |
9 |
Correct |
2 ms |
5024 KB |
Output is correct |
10 |
Correct |
3 ms |
4948 KB |
Output is correct |
11 |
Correct |
4 ms |
5024 KB |
Output is correct |
12 |
Correct |
3 ms |
4948 KB |
Output is correct |
13 |
Correct |
4 ms |
5028 KB |
Output is correct |
14 |
Correct |
3 ms |
4948 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
5024 KB |
Output is correct |
17 |
Correct |
3 ms |
5024 KB |
Output is correct |
18 |
Correct |
3 ms |
5024 KB |
Output is correct |
19 |
Correct |
4 ms |
4948 KB |
Output is correct |
20 |
Correct |
3 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
4948 KB |
Output is correct |
22 |
Correct |
3 ms |
5032 KB |
Output is correct |
23 |
Correct |
5 ms |
5428 KB |
Output is correct |
24 |
Correct |
6 ms |
5420 KB |
Output is correct |
25 |
Correct |
6 ms |
5420 KB |
Output is correct |
26 |
Correct |
10 ms |
5936 KB |
Output is correct |
27 |
Correct |
10 ms |
5932 KB |
Output is correct |
28 |
Correct |
7 ms |
5968 KB |
Output is correct |
29 |
Correct |
8 ms |
5940 KB |
Output is correct |
30 |
Correct |
7 ms |
5936 KB |
Output is correct |
31 |
Correct |
7 ms |
6316 KB |
Output is correct |
32 |
Correct |
33 ms |
9804 KB |
Output is correct |
33 |
Correct |
28 ms |
9868 KB |
Output is correct |
34 |
Correct |
28 ms |
9812 KB |
Output is correct |
35 |
Correct |
209 ms |
24992 KB |
Output is correct |
36 |
Correct |
209 ms |
25000 KB |
Output is correct |
37 |
Correct |
197 ms |
25144 KB |
Output is correct |
38 |
Correct |
124 ms |
24240 KB |
Output is correct |
39 |
Correct |
139 ms |
24092 KB |
Output is correct |
40 |
Correct |
119 ms |
24268 KB |
Output is correct |
41 |
Correct |
175 ms |
29576 KB |
Output is correct |