#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <cassert>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <numeric>
using namespace std;
#define int long long
void maxup(int& a, int b)
{
a = max(a, b);
}
const int N = 200000 + 7;
const int INF = (int)1e18 + 7;
int n;
int par[N];
int parval[N];
vector<pair<int, int>> ginit[N];
vector<int> g[N];
int dp[N][2][2]; // dp[a][taken up][has bb]
void build(int a, int p = 0)
{
vector<int> kids;
for (auto& it : ginit[a])
{
int b = it.first, c = it.second;
if (b == p)
{
continue;
}
build(b, a);
par[b] = a;
parval[b] = c;
kids.push_back(b);
}
g[a] = kids;
}
int get(int a, bool okup, bool okhas)
{
int sol = 0;
maxup(sol, dp[a][0][0]);
if (okup) maxup(sol, dp[a][1][0]);
if (okhas) maxup(sol, dp[a][0][1]);
if (okup && okhas) maxup(sol, dp[a][1][1]);
return sol;
}
int best[5][5][5]; // how many legs and how many downs and how many downs from legs
int newbest[5][5][5]; // how many legs and how many downs and how many downs from legs
void clr()
{
for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++)for (int k = 0; k < 2; k++) best[i][j][k] = newbest[i][j][k] = -INF;
best[0][0][0] = 0;
}
void swp()
{
for (int i = 0; i < 3; i++) for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) best[i][j][k] = newbest[i][j][k], newbest[i][j][k] = -INF;
}
void solve(int a)
{
for (auto& b : g[a])
{
solve(b);
}
clr();
for (auto& b : g[a])
{
for (int leg = 0; leg < 3; leg++)
{
for (int dw = 0; dw < 2; dw++)
{
for (int dwl = 0; dwl < 2; dwl++)
{
for (int l2 = 0; l2 <= 1; l2++)
{
for (int d2 = 0; d2 <= 1; d2++)
{
int val = best[leg][dw][dwl] + get(b, !l2, d2) + l2 * parval[b];
maxup(newbest[leg + l2][dw + d2 * (l2 == 0)][dwl + d2 * (l2 == 1)], val);
}
}
}
}
}
swp();
}
{
// nu am nimic
maxup(dp[a][0][0], best[0][0][0]);
maxup(dp[a][0][1], best[0][1][0]);
}
{
// am doua picioare
maxup(dp[a][0][1], best[2][0][0]);
maxup(dp[a][0][1], best[2][0][1]);
}
if (par[a])
{
// am un picior
maxup(dp[a][1][0], best[1][0][0] + parval[a]);
maxup(dp[a][1][1], best[1][0][1] + parval[a]);
}
}
signed main()
{
#ifdef ONPC
FILE* stream;
freopen_s(&stream, "input.txt", "r", stdin);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
cin >> n;
for (int i = 1; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
ginit[a].push_back({ b, c });
ginit[b].push_back({ a, c });
}
build(1);
solve(1);
cout << get(1, 1, 1) << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9688 KB |
Output is correct |
11 |
Correct |
6 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9688 KB |
Output is correct |
11 |
Correct |
6 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9736 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9684 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
5 ms |
9684 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
5 ms |
9760 KB |
Output is correct |
20 |
Correct |
7 ms |
9684 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
22 |
Correct |
6 ms |
9684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9688 KB |
Output is correct |
11 |
Correct |
6 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9736 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9684 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
5 ms |
9684 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
5 ms |
9760 KB |
Output is correct |
20 |
Correct |
7 ms |
9684 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
22 |
Correct |
6 ms |
9684 KB |
Output is correct |
23 |
Correct |
9 ms |
10204 KB |
Output is correct |
24 |
Correct |
9 ms |
10316 KB |
Output is correct |
25 |
Correct |
9 ms |
10196 KB |
Output is correct |
26 |
Correct |
13 ms |
10844 KB |
Output is correct |
27 |
Correct |
13 ms |
10836 KB |
Output is correct |
28 |
Correct |
12 ms |
10828 KB |
Output is correct |
29 |
Correct |
11 ms |
10824 KB |
Output is correct |
30 |
Correct |
12 ms |
10836 KB |
Output is correct |
31 |
Correct |
13 ms |
11348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9684 KB |
Output is correct |
2 |
Correct |
5 ms |
9684 KB |
Output is correct |
3 |
Correct |
5 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
6 ms |
9684 KB |
Output is correct |
8 |
Correct |
5 ms |
9684 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9688 KB |
Output is correct |
11 |
Correct |
6 ms |
9684 KB |
Output is correct |
12 |
Correct |
5 ms |
9736 KB |
Output is correct |
13 |
Correct |
5 ms |
9684 KB |
Output is correct |
14 |
Correct |
5 ms |
9684 KB |
Output is correct |
15 |
Correct |
5 ms |
9684 KB |
Output is correct |
16 |
Correct |
5 ms |
9684 KB |
Output is correct |
17 |
Correct |
5 ms |
9684 KB |
Output is correct |
18 |
Correct |
5 ms |
9684 KB |
Output is correct |
19 |
Correct |
5 ms |
9760 KB |
Output is correct |
20 |
Correct |
7 ms |
9684 KB |
Output is correct |
21 |
Correct |
5 ms |
9684 KB |
Output is correct |
22 |
Correct |
6 ms |
9684 KB |
Output is correct |
23 |
Correct |
9 ms |
10204 KB |
Output is correct |
24 |
Correct |
9 ms |
10316 KB |
Output is correct |
25 |
Correct |
9 ms |
10196 KB |
Output is correct |
26 |
Correct |
13 ms |
10844 KB |
Output is correct |
27 |
Correct |
13 ms |
10836 KB |
Output is correct |
28 |
Correct |
12 ms |
10828 KB |
Output is correct |
29 |
Correct |
11 ms |
10824 KB |
Output is correct |
30 |
Correct |
12 ms |
10836 KB |
Output is correct |
31 |
Correct |
13 ms |
11348 KB |
Output is correct |
32 |
Correct |
56 ms |
15484 KB |
Output is correct |
33 |
Correct |
60 ms |
15484 KB |
Output is correct |
34 |
Correct |
49 ms |
15388 KB |
Output is correct |
35 |
Correct |
259 ms |
32752 KB |
Output is correct |
36 |
Correct |
288 ms |
32656 KB |
Output is correct |
37 |
Correct |
266 ms |
32720 KB |
Output is correct |
38 |
Correct |
188 ms |
32188 KB |
Output is correct |
39 |
Correct |
196 ms |
31364 KB |
Output is correct |
40 |
Correct |
180 ms |
31396 KB |
Output is correct |
41 |
Correct |
242 ms |
39236 KB |
Output is correct |