//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;
void solve(){
int n; cin >> n;
vector<vector<T>>g(n+1);
for (int i = 1; i<n; i++){
int a, b, c; cin >> a >> b >> c;
g[a].emplace_back(b, c);
g[b].emplace_back(a, c);
}
//pomiedzy kazda para wisienek sciezka laczaca ich srodki musi przechodzic przez inny wierzcholek jakiejs wisienki jeszcze
//dp[v][0] -> jest wisienka w poddrzewie, nie uzywamy krawedzi do rodzica
//dp[v][1] -> jest wisienka w poddrzewie, uzywamy krawedzi do rodzica
//dp[v][2] -> nie ma wisienki w poddrzewie, nie uzywamy krawedzi do rodzica
//dp[v][3] -> nie ma wisienki w poddrzewie, uzywamy krawedz do rodzica
vector dp(n+1, vector<int>(4));
function<void(int, int, int)>dfs = [&](int v, int pa, int cc){
for (auto [x, c]: g[v]){
if (x == pa) continue;
dfs(x, v, c);
dp[v][2] += max(dp[x][2], dp[x][3]);
}
for (auto [x, c]: g[v]){
dp[v][0] = max(dp[v][0], dp[v][2]+max(dp[x][0], dp[x][1])-max(dp[x][2], dp[x][3]));
}
//dp[v][0] -> robimy wisienke w wierzcholku v -> maksymalnie jeden syn wisienki moze miec dp[x][0]
//dp[v][0] = dp[v][2] + [dp[x][0] - max(dp[x][2], dp[x][3]) + c1] + [dp[x][2]-max(dp[x][2], dp[x][3]) + c2]
//dp[v][1] -> 1) dp[v][2] + [dp[x][0] - max(dp[x][2], dp[x][3]) + c] + cc (gdy ta jedna wisienka w poddrzewie x)
//lub dp[v][2] + [dp[x][2] - max(dp[x][2], dp[x][3]) + c] + cc + [max(dp[x][0], dp[x][1]) - max(dp[x][2], dp[x][3])];
vector<T>mx(2, {-oo, -oo});
for (auto [x2, c2]: g[v]){
if (x2 == pa) continue;
T val = {dp[x2][2]-max(dp[x2][2], dp[x2][3]) + c2, x2};
if (val >= mx[0]) swap(val, mx[0]);
if (val >= mx[1]) swap(val, mx[1]);
}
for (auto [x1, c1]: g[v]){
if (x1 == pa) continue;
dp[v][1] = max(dp[v][1], dp[v][2] + (dp[x1][0] - max(dp[x1][2], dp[x1][3]) + c1) + cc);
dp[v][0] = max(dp[v][0],
dp[v][2] + (dp[x1][0] - max(dp[x1][2], dp[x1][3]) +c1) + (mx[0].second == x1 ? mx[1].first : mx[0].first));
// for (auto [x2, c2]: g[v]){
// if (x2 == pa || x2 == x1) continue;
//tu uzywam tego rozroznienia zeby moc uzyc faktu ze nie ma krawedzi do rodzica
// dp[v][1] = max(dp[v][1],
// dp[v][2] + (dp[x1][2] - max(dp[x1][2], dp[x1][3]) + c1) + cc + (max(dp[x2][0], dp[x2][1]) - max(dp[x2][2], dp[x2][3]))); -> nie moge tego uzyc bo powstaje polaczenie pomiedzy srodkami pionowej i w poddrzewie wisienki
// }
}
//dp[v][3] = dp[v][2] + cc + [dp[x][2] - max(dp[x][2], dp[x][3]) + c]
for (auto [x, c]: g[v]){
if (x == pa) continue;
dp[v][3] = max(dp[v][3], dp[v][2]+cc+dp[x][2]-max(dp[x][2], dp[x][3])+c);
}
debug(v, dp[v]);
};
dfs(1, 1, -oo);
cout << max(dp[1][0], dp[1][2]) << "\n";
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
456 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
456 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
456 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
3 ms |
1376 KB |
Output is correct |
24 |
Correct |
2 ms |
1116 KB |
Output is correct |
25 |
Correct |
2 ms |
1116 KB |
Output is correct |
26 |
Correct |
5 ms |
1884 KB |
Output is correct |
27 |
Correct |
4 ms |
1884 KB |
Output is correct |
28 |
Correct |
4 ms |
2008 KB |
Output is correct |
29 |
Correct |
4 ms |
1884 KB |
Output is correct |
30 |
Correct |
4 ms |
2000 KB |
Output is correct |
31 |
Correct |
5 ms |
2396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
456 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
456 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
3 ms |
1376 KB |
Output is correct |
24 |
Correct |
2 ms |
1116 KB |
Output is correct |
25 |
Correct |
2 ms |
1116 KB |
Output is correct |
26 |
Correct |
5 ms |
1884 KB |
Output is correct |
27 |
Correct |
4 ms |
1884 KB |
Output is correct |
28 |
Correct |
4 ms |
2008 KB |
Output is correct |
29 |
Correct |
4 ms |
1884 KB |
Output is correct |
30 |
Correct |
4 ms |
2000 KB |
Output is correct |
31 |
Correct |
5 ms |
2396 KB |
Output is correct |
32 |
Correct |
21 ms |
8280 KB |
Output is correct |
33 |
Correct |
21 ms |
8284 KB |
Output is correct |
34 |
Correct |
23 ms |
8540 KB |
Output is correct |
35 |
Correct |
147 ms |
32848 KB |
Output is correct |
36 |
Correct |
163 ms |
33092 KB |
Output is correct |
37 |
Correct |
131 ms |
32852 KB |
Output is correct |
38 |
Correct |
123 ms |
32376 KB |
Output is correct |
39 |
Correct |
133 ms |
32020 KB |
Output is correct |
40 |
Correct |
119 ms |
32252 KB |
Output is correct |
41 |
Correct |
153 ms |
38080 KB |
Output is correct |