#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int N=2e5+1;
int n;
int dp[N][4];
int p[N],pl[N];
int z[4];
vector<pair<int,int> >adj[N];
void dfs(int id){
for(auto cur:adj[id]){
if(cur.se==p[id]) continue;
p[cur.se]=id,pl[cur.se]=cur.fi;
dfs(cur.se);
}
}
void solve(int id){
z[0]=z[1]=z[2]=z[3]=-2e9;z[1]=0;
for(auto cur:adj[id]){//doesnt take node i as merger
if(cur.se==p[id]) continue;
solve(cur.se);
z[3]=max(z[3]+max(dp[cur.se][0],dp[cur.se][1]),z[1]+max(dp[cur.se][2],dp[cur.se][3]));
z[1]=z[1]+max(dp[cur.se][0],dp[cur.se][1]);
}
dp[id][1]=max(dp[id][1],z[1]);dp[id][3]=max(dp[id][3],z[3]);
z[0]=z[1]=z[2]=z[3]=-2e9;z[0]=0;
for(auto cur:adj[id]){//merge horizontally
if(cur.se==p[id]) continue;
z[3]=z[3]+max(dp[cur.se][0],dp[cur.se][1]);
z[3]=max(z[3],max(z[2]+dp[cur.se][1],z[1]+max(dp[cur.se][1],dp[cur.se][3]))+pl[cur.se]);
z[2]=max(z[2]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+max(dp[cur.se][1],dp[cur.se][3])+pl[cur.se]);
z[1]=max(z[1]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+dp[cur.se][1]+pl[cur.se]);
z[0]=z[0]+max(dp[cur.se][0],dp[cur.se][1]);
}
dp[id][3]=max(dp[id][3],z[3]);
if(id==1) return;
z[0]=z[1]=z[2]=z[3]=-2e9;z[0]=0;
for(auto cur:adj[id]){//merge vertically
if(cur.se==p[id]) continue;
z[2]=max(z[2]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+max(dp[cur.se][3],dp[cur.se][1])+pl[cur.se]);
z[1]=max(z[1]+max(dp[cur.se][0],dp[cur.se][1]),z[0]+dp[cur.se][1]+pl[cur.se]);
z[0]=z[0]+max(dp[cur.se][0],dp[cur.se][1]);
}
dp[id][2]=max(dp[id][2],z[2]+pl[id]);dp[id][0]=max(dp[id][0],z[1]+pl[id]);
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
for(int i=1; i<n ;i++){
int u,v,w;cin >> u >> v >> w;
adj[u].pb({w,v});adj[v].pb({w,u});
}
dfs(1);
solve(1);
cout << max(max(dp[1][0],dp[1][1]),max(dp[1][2],dp[1][3])) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4992 KB |
Output is correct |
2 |
Correct |
5 ms |
4992 KB |
Output is correct |
3 |
Incorrect |
6 ms |
5120 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |