#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
const int maxn = 2e5+5;
const ll inf = 1e15;
ll dp[maxn][4];
// 1st mask: across edge
// 2nd mask: require upedge
int n;
vector<pair<int, int>> tree[maxn];
void dfs(int x, int p, int w){
if(x != 1 && tree[x].size() == 1){
dp[x][1]=w;
dp[x][2]=-inf;
dp[x][3]=-inf;
}
else{
ll best[4], sum = 0;
for(int i = 0; i < 4; i++)best[i]=dp[x][i]=-inf;
// 00 : all 00 or one 01 + w
// 01: all 00 + w
// 10: one 11, all 00+w || one 11, one 01,all 00 || two 01, all 00 || one 10, all 00
// 11: (one 10, all 00 || one 11, one 01,all 00 || two 01, all 00)+w
for(auto v: tree[x]){
if(v.f == p)continue;
dfs(v.f, x, v.s);
ll base = dp[v.f][0];
sum+=base;
for(int i = 0; i< 4; i++)dp[v.f][i]-=base;
dp[x][3] = max(dp[x][3], best[3] + dp[v.f][1]);
dp[x][3] = max(dp[x][3], best[1] + dp[v.f][3]);
dp[x][3] = max(dp[x][3], best[1] + dp[v.f][1]);
for(int i = 0; i< 4; i++)best[i]=max(best[i], dp[v.f][i]);
}
dp[x][0] = max(best[1]+w, 0LL)+sum;
dp[x][1] = sum + w;
dp[x][2] = max({dp[x][3], best[2], best[3]+w})+sum;
dp[x][3] = max(dp[x][3], best[2])+sum+w;
//for(int i = 0; i < 4; i++)cout << x << " " << i << " " << dp[x][i] << "\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//ifstream cin("input.txt");
cin >> n;
for(int i = 1; i < n; i++){
int a, b, w;
cin >> a >> b >> w;
tree[a].push_back({b, w});
tree[b].push_back({a, w});
}
dfs(1, 0, 0);
cout << max(dp[1][1] , dp[1][3]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
4 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
5036 KB |
Output is correct |
10 |
Correct |
4 ms |
4948 KB |
Output is correct |
11 |
Correct |
5 ms |
5040 KB |
Output is correct |
12 |
Correct |
4 ms |
5040 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
4 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
5036 KB |
Output is correct |
10 |
Correct |
4 ms |
4948 KB |
Output is correct |
11 |
Correct |
5 ms |
5040 KB |
Output is correct |
12 |
Correct |
4 ms |
5040 KB |
Output is correct |
13 |
Correct |
4 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5032 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
5032 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
4 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
5036 KB |
Output is correct |
22 |
Correct |
5 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
4 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
5036 KB |
Output is correct |
10 |
Correct |
4 ms |
4948 KB |
Output is correct |
11 |
Correct |
5 ms |
5040 KB |
Output is correct |
12 |
Correct |
4 ms |
5040 KB |
Output is correct |
13 |
Correct |
4 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5032 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
5032 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
4 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
5036 KB |
Output is correct |
22 |
Correct |
5 ms |
4948 KB |
Output is correct |
23 |
Correct |
19 ms |
5396 KB |
Output is correct |
24 |
Correct |
8 ms |
5332 KB |
Output is correct |
25 |
Correct |
8 ms |
5352 KB |
Output is correct |
26 |
Correct |
10 ms |
5844 KB |
Output is correct |
27 |
Correct |
12 ms |
5876 KB |
Output is correct |
28 |
Correct |
10 ms |
5808 KB |
Output is correct |
29 |
Correct |
11 ms |
5816 KB |
Output is correct |
30 |
Correct |
11 ms |
5816 KB |
Output is correct |
31 |
Correct |
11 ms |
6464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
4948 KB |
Output is correct |
2 |
Correct |
4 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
4 ms |
4948 KB |
Output is correct |
5 |
Correct |
4 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
4 ms |
4948 KB |
Output is correct |
8 |
Correct |
4 ms |
4940 KB |
Output is correct |
9 |
Correct |
4 ms |
5036 KB |
Output is correct |
10 |
Correct |
4 ms |
4948 KB |
Output is correct |
11 |
Correct |
5 ms |
5040 KB |
Output is correct |
12 |
Correct |
4 ms |
5040 KB |
Output is correct |
13 |
Correct |
4 ms |
5076 KB |
Output is correct |
14 |
Correct |
3 ms |
5032 KB |
Output is correct |
15 |
Correct |
3 ms |
4948 KB |
Output is correct |
16 |
Correct |
3 ms |
4948 KB |
Output is correct |
17 |
Correct |
3 ms |
5032 KB |
Output is correct |
18 |
Correct |
3 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
4 ms |
4948 KB |
Output is correct |
21 |
Correct |
4 ms |
5036 KB |
Output is correct |
22 |
Correct |
5 ms |
4948 KB |
Output is correct |
23 |
Correct |
19 ms |
5396 KB |
Output is correct |
24 |
Correct |
8 ms |
5332 KB |
Output is correct |
25 |
Correct |
8 ms |
5352 KB |
Output is correct |
26 |
Correct |
10 ms |
5844 KB |
Output is correct |
27 |
Correct |
12 ms |
5876 KB |
Output is correct |
28 |
Correct |
10 ms |
5808 KB |
Output is correct |
29 |
Correct |
11 ms |
5816 KB |
Output is correct |
30 |
Correct |
11 ms |
5816 KB |
Output is correct |
31 |
Correct |
11 ms |
6464 KB |
Output is correct |
32 |
Correct |
39 ms |
9116 KB |
Output is correct |
33 |
Correct |
33 ms |
9164 KB |
Output is correct |
34 |
Correct |
36 ms |
9084 KB |
Output is correct |
35 |
Correct |
172 ms |
22260 KB |
Output is correct |
36 |
Correct |
157 ms |
22220 KB |
Output is correct |
37 |
Correct |
188 ms |
22228 KB |
Output is correct |
38 |
Correct |
147 ms |
22612 KB |
Output is correct |
39 |
Correct |
98 ms |
22552 KB |
Output is correct |
40 |
Correct |
105 ms |
22460 KB |
Output is correct |
41 |
Correct |
181 ms |
28968 KB |
Output is correct |