#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const ll N=2e5+5;
ll dp[2][N];
vector<pair<ll,ll>>adj[N];
vector<ll>ord;
void dfs(ll v,ll par){
ord.pb(v);
for(auto [u,w]:adj[v]){
if(u!=par){
dp[1][u]=w;
dfs(u,v);
ord.pb(v);
dp[0][v]=max(dp[0][v]+dp[0][u],dp[1][v]+dp[1][u]);
dp[1][v]+=dp[0][u];
}
}
}
void cal(ll root,ll newRoot){
ll d=0;
for(auto [i,w]:adj[root]){
if(i==newRoot){
d=w;
break;
}
}
dp[1][root]=d;
dp[0][root]=0;
dp[0][newRoot]=0;
dp[1][newRoot]=0;
for(auto [i,w]:adj[root]){
if(i!=newRoot){
dp[0][root]=max(dp[0][root]+dp[0][i],dp[1][root]+dp[1][i]);
dp[1][root]+=dp[0][i];
}
}
for(auto [i,w]:adj[newRoot]){
dp[0][newRoot]=max(dp[0][newRoot]+dp[0][i],dp[1][newRoot]+dp[1][i]);
dp[1][newRoot]+=dp[0][i];
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll n;
cin>>n;
for(ll i=1;i<n;i++){
ll u,v,w;
cin>>u>>v>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
fill(dp[0],dp[0]+n+1,0);
fill(dp[1],dp[1]+n+1,0);
dfs(1,-1);
ll ans=dp[1][1];
for(ll r=1;r<ord.size();r++){
if(ord[r-1]!=ord[r]){
cal(ord[r-1],ord[r]);
ans=max(ans,dp[1][ord[r]]);
}
}
cout<<ans;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:66:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
66 | for(ll r=1;r<ord.size();r++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6756 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6792 KB |
Output is correct |
5 |
Correct |
1 ms |
6796 KB |
Output is correct |
6 |
Correct |
1 ms |
6748 KB |
Output is correct |
7 |
Correct |
1 ms |
6748 KB |
Output is correct |
8 |
Correct |
1 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6744 KB |
Output is correct |
11 |
Correct |
1 ms |
6744 KB |
Output is correct |
12 |
Correct |
1 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6756 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6792 KB |
Output is correct |
5 |
Correct |
1 ms |
6796 KB |
Output is correct |
6 |
Correct |
1 ms |
6748 KB |
Output is correct |
7 |
Correct |
1 ms |
6748 KB |
Output is correct |
8 |
Correct |
1 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6744 KB |
Output is correct |
11 |
Correct |
1 ms |
6744 KB |
Output is correct |
12 |
Correct |
1 ms |
6748 KB |
Output is correct |
13 |
Correct |
2 ms |
6744 KB |
Output is correct |
14 |
Correct |
2 ms |
6744 KB |
Output is correct |
15 |
Correct |
2 ms |
6744 KB |
Output is correct |
16 |
Correct |
1 ms |
6748 KB |
Output is correct |
17 |
Correct |
2 ms |
6748 KB |
Output is correct |
18 |
Correct |
3 ms |
6748 KB |
Output is correct |
19 |
Correct |
2 ms |
6748 KB |
Output is correct |
20 |
Correct |
2 ms |
6748 KB |
Output is correct |
21 |
Correct |
1 ms |
6748 KB |
Output is correct |
22 |
Correct |
1 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6756 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6792 KB |
Output is correct |
5 |
Correct |
1 ms |
6796 KB |
Output is correct |
6 |
Correct |
1 ms |
6748 KB |
Output is correct |
7 |
Correct |
1 ms |
6748 KB |
Output is correct |
8 |
Correct |
1 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6744 KB |
Output is correct |
11 |
Correct |
1 ms |
6744 KB |
Output is correct |
12 |
Correct |
1 ms |
6748 KB |
Output is correct |
13 |
Correct |
2 ms |
6744 KB |
Output is correct |
14 |
Correct |
2 ms |
6744 KB |
Output is correct |
15 |
Correct |
2 ms |
6744 KB |
Output is correct |
16 |
Correct |
1 ms |
6748 KB |
Output is correct |
17 |
Correct |
2 ms |
6748 KB |
Output is correct |
18 |
Correct |
3 ms |
6748 KB |
Output is correct |
19 |
Correct |
2 ms |
6748 KB |
Output is correct |
20 |
Correct |
2 ms |
6748 KB |
Output is correct |
21 |
Correct |
1 ms |
6748 KB |
Output is correct |
22 |
Correct |
1 ms |
6748 KB |
Output is correct |
23 |
Correct |
3 ms |
7256 KB |
Output is correct |
24 |
Correct |
3 ms |
7260 KB |
Output is correct |
25 |
Correct |
3 ms |
7184 KB |
Output is correct |
26 |
Correct |
6 ms |
7772 KB |
Output is correct |
27 |
Correct |
6 ms |
7784 KB |
Output is correct |
28 |
Correct |
284 ms |
7636 KB |
Output is correct |
29 |
Correct |
125 ms |
7772 KB |
Output is correct |
30 |
Correct |
92 ms |
7768 KB |
Output is correct |
31 |
Correct |
56 ms |
8024 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6756 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6792 KB |
Output is correct |
5 |
Correct |
1 ms |
6796 KB |
Output is correct |
6 |
Correct |
1 ms |
6748 KB |
Output is correct |
7 |
Correct |
1 ms |
6748 KB |
Output is correct |
8 |
Correct |
1 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6744 KB |
Output is correct |
11 |
Correct |
1 ms |
6744 KB |
Output is correct |
12 |
Correct |
1 ms |
6748 KB |
Output is correct |
13 |
Correct |
2 ms |
6744 KB |
Output is correct |
14 |
Correct |
2 ms |
6744 KB |
Output is correct |
15 |
Correct |
2 ms |
6744 KB |
Output is correct |
16 |
Correct |
1 ms |
6748 KB |
Output is correct |
17 |
Correct |
2 ms |
6748 KB |
Output is correct |
18 |
Correct |
3 ms |
6748 KB |
Output is correct |
19 |
Correct |
2 ms |
6748 KB |
Output is correct |
20 |
Correct |
2 ms |
6748 KB |
Output is correct |
21 |
Correct |
1 ms |
6748 KB |
Output is correct |
22 |
Correct |
1 ms |
6748 KB |
Output is correct |
23 |
Correct |
3 ms |
7256 KB |
Output is correct |
24 |
Correct |
3 ms |
7260 KB |
Output is correct |
25 |
Correct |
3 ms |
7184 KB |
Output is correct |
26 |
Correct |
6 ms |
7772 KB |
Output is correct |
27 |
Correct |
6 ms |
7784 KB |
Output is correct |
28 |
Correct |
284 ms |
7636 KB |
Output is correct |
29 |
Correct |
125 ms |
7772 KB |
Output is correct |
30 |
Correct |
92 ms |
7768 KB |
Output is correct |
31 |
Correct |
56 ms |
8024 KB |
Output is correct |
32 |
Correct |
20 ms |
11412 KB |
Output is correct |
33 |
Correct |
21 ms |
11472 KB |
Output is correct |
34 |
Correct |
21 ms |
11476 KB |
Output is correct |
35 |
Correct |
149 ms |
26408 KB |
Output is correct |
36 |
Correct |
124 ms |
26568 KB |
Output is correct |
37 |
Correct |
119 ms |
27904 KB |
Output is correct |
38 |
Execution timed out |
1049 ms |
30396 KB |
Time limit exceeded |
39 |
Halted |
0 ms |
0 KB |
- |