#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=2*1e5,mod=1000000007,lg=25,root=1000,inf=1e18;
int dp[mxn+10][2][2],up[mxn+10];
//state:cnt 1,2/found,not found root
vector<pii>adj[mxn+10];
void solve(int cur,int p){
if(adj[cur].size()<=1&&p!=-1)return;
vector<pii>v1,v2;
int other=0,mx=0;
for(auto i:adj[cur]){
if(i.f==p)continue;
up[i.f]=i.s;
solve(i.f,cur);
int mx1=max(dp[i.f][0][0],dp[i.f][1][0]);
other+=mx1;
mx=max(mx,max(dp[i.f][1][1],dp[i.f][0][1])-mx1);
v1.pb({dp[i.f][1][0]-mx1+i.s,i.f});
v2.pb({dp[i.f][1][1]-mx1+i.s,i.f});
}
sort(rall(v1));
sort(rall(v2));
dp[cur][0][0]=other+v1[0].f+up[cur];
dp[cur][1][0]=other;
if(p!=-1)dp[cur][0][1]=v2[0].f+other+up[cur];//cnt 1
else dp[cur][0][1]=other;
dp[cur][1][1]=other+mx;//continue
if(v1.size()>1)dp[cur][1][1]=max(dp[cur][1][1],other+v1[0].f+v1[1].f);//make
if(v1[0].s!=v2[0].s)dp[cur][1][1]=max(dp[cur][1][1],other+v1[0].f+v2[0].f);
else if(v1.size()>1)dp[cur][1][1]=max(dp[cur][1][1],other+max(v1[0].f+v2[1].f,v1[1].f+v2[0].f));
//0 0
}
/*
0
1->max(2,1)+one (2)+i.s+up
2->max(2,1)
1
2->make->two 2 notfound+i.s
1->one
*/
int32_t main(){
fastio
int n;cin>>n;
for(int i=0;i<n-1;i++){
int u,v,w;cin>>u>>v>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
solve(1,-1);
cout<<max(dp[1][0][1],dp[1][1][1])<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
2 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 |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6748 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
2 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 |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6748 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
13 |
Correct |
1 ms |
6744 KB |
Output is correct |
14 |
Correct |
2 ms |
6744 KB |
Output is correct |
15 |
Correct |
1 ms |
6744 KB |
Output is correct |
16 |
Correct |
1 ms |
6748 KB |
Output is correct |
17 |
Correct |
1 ms |
6748 KB |
Output is correct |
18 |
Correct |
1 ms |
6748 KB |
Output is correct |
19 |
Correct |
1 ms |
6748 KB |
Output is correct |
20 |
Correct |
1 ms |
6748 KB |
Output is correct |
21 |
Correct |
1 ms |
6748 KB |
Output is correct |
22 |
Correct |
2 ms |
6748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
2 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 |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6748 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
13 |
Correct |
1 ms |
6744 KB |
Output is correct |
14 |
Correct |
2 ms |
6744 KB |
Output is correct |
15 |
Correct |
1 ms |
6744 KB |
Output is correct |
16 |
Correct |
1 ms |
6748 KB |
Output is correct |
17 |
Correct |
1 ms |
6748 KB |
Output is correct |
18 |
Correct |
1 ms |
6748 KB |
Output is correct |
19 |
Correct |
1 ms |
6748 KB |
Output is correct |
20 |
Correct |
1 ms |
6748 KB |
Output is correct |
21 |
Correct |
1 ms |
6748 KB |
Output is correct |
22 |
Correct |
2 ms |
6748 KB |
Output is correct |
23 |
Correct |
3 ms |
7000 KB |
Output is correct |
24 |
Correct |
3 ms |
9052 KB |
Output is correct |
25 |
Correct |
3 ms |
9104 KB |
Output is correct |
26 |
Correct |
5 ms |
9356 KB |
Output is correct |
27 |
Correct |
5 ms |
7516 KB |
Output is correct |
28 |
Correct |
6 ms |
8152 KB |
Output is correct |
29 |
Correct |
5 ms |
7768 KB |
Output is correct |
30 |
Correct |
5 ms |
8004 KB |
Output is correct |
31 |
Correct |
8 ms |
8628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6748 KB |
Output is correct |
2 |
Correct |
1 ms |
6748 KB |
Output is correct |
3 |
Correct |
1 ms |
6748 KB |
Output is correct |
4 |
Correct |
1 ms |
6748 KB |
Output is correct |
5 |
Correct |
1 ms |
6748 KB |
Output is correct |
6 |
Correct |
2 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 |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6748 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
13 |
Correct |
1 ms |
6744 KB |
Output is correct |
14 |
Correct |
2 ms |
6744 KB |
Output is correct |
15 |
Correct |
1 ms |
6744 KB |
Output is correct |
16 |
Correct |
1 ms |
6748 KB |
Output is correct |
17 |
Correct |
1 ms |
6748 KB |
Output is correct |
18 |
Correct |
1 ms |
6748 KB |
Output is correct |
19 |
Correct |
1 ms |
6748 KB |
Output is correct |
20 |
Correct |
1 ms |
6748 KB |
Output is correct |
21 |
Correct |
1 ms |
6748 KB |
Output is correct |
22 |
Correct |
2 ms |
6748 KB |
Output is correct |
23 |
Correct |
3 ms |
7000 KB |
Output is correct |
24 |
Correct |
3 ms |
9052 KB |
Output is correct |
25 |
Correct |
3 ms |
9104 KB |
Output is correct |
26 |
Correct |
5 ms |
9356 KB |
Output is correct |
27 |
Correct |
5 ms |
7516 KB |
Output is correct |
28 |
Correct |
6 ms |
8152 KB |
Output is correct |
29 |
Correct |
5 ms |
7768 KB |
Output is correct |
30 |
Correct |
5 ms |
8004 KB |
Output is correct |
31 |
Correct |
8 ms |
8628 KB |
Output is correct |
32 |
Correct |
20 ms |
11500 KB |
Output is correct |
33 |
Correct |
20 ms |
11612 KB |
Output is correct |
34 |
Correct |
30 ms |
11664 KB |
Output is correct |
35 |
Correct |
126 ms |
26704 KB |
Output is correct |
36 |
Correct |
112 ms |
26712 KB |
Output is correct |
37 |
Correct |
105 ms |
26708 KB |
Output is correct |
38 |
Correct |
111 ms |
36532 KB |
Output is correct |
39 |
Correct |
109 ms |
26236 KB |
Output is correct |
40 |
Correct |
106 ms |
30724 KB |
Output is correct |
41 |
Correct |
126 ms |
40124 KB |
Output is correct |