#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ll> vi;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int N = 333333;
vector<ii> adj[N];
int dp[N][2];
const int INF = int(1e9);
int dp2[N][2];
void dfs(int u, int p)
{
vi pre(2,-INF); pre[0]=0;
dp[u][0]=dp[u][1]=-INF;
for(ii X:adj[u])
{
int v=X.fi; int w=X.se;
if(v==p) continue;
dfs(v,u);
vi nw(2,-INF);
nw[0]=max(nw[0],pre[0]+dp[v][0]);
nw[1]=max(nw[1],pre[1]+dp[v][0]);
nw[0]=max(nw[0],pre[0]+w+dp[v][1]);
nw[1]=max(nw[1],pre[0]+w+dp[v][0]);
nw[1]=max(nw[1],pre[1]+w+dp[v][1]);
pre=nw;
}
dp[u][0]=pre[0]; dp[u][1]=pre[1];
//cerr<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<'\n';
}
void dfs2(int u, int p)
{
int sum=dp2[u][0];
vector<ii> vec;
vec.pb({dp2[u][1]-dp2[u][0],u});
for(ii X:adj[u])
{
int v=X.fi; int w=X.se;
if(v==p) continue;
sum+=max(dp[v][0],dp[v][1]+w);
int nwval = dp[v][0]+w;
vec.pb({nwval-max(dp[v][0],dp[v][1]+w),v});
}
sort(vec.rbegin(),vec.rend());
for(ii X:adj[u])
{
int v=X.fi; int w=X.se;
if(v==p) continue;
//compute dp2[v][0], dp2[v][1]
dp2[v][1]=-INF;
sum-=max(dp[v][0],dp[v][1]+w);
if(w+sum>=0) dp2[v][1]=w+sum;
dp2[v][0]=sum;
int largest=vec[0].fi;
if(vec[0].se==v)
{
if(vec.size()<=1) largest=-INF;
else largest=vec[1].fi;
}
dp2[v][0]=max(dp2[v][0],w+sum+largest);
sum+=max(dp[v][0],dp[v][1]+w);
dfs2(v,u);
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin>>n;
for(int i=0;i<n-1;i++)
{
int u,v; cin>>u>>v; u--; v--;
int w; cin>>w;
adj[u].pb({v,w});
adj[v].pb({u,w});
}
int ans=0;
dfs(0,-1);
dp2[0][0]=0; dp2[0][1]=-INF;
dfs2(0,-1);
for(int i=0;i<n;i++)
{
ans=max(ans,dp[i][0]+dp2[i][0]);
}
cout<<ans<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8192 KB |
Output is correct |
3 |
Correct |
9 ms |
8192 KB |
Output is correct |
4 |
Correct |
9 ms |
8192 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
8 ms |
8192 KB |
Output is correct |
7 |
Correct |
9 ms |
8192 KB |
Output is correct |
8 |
Correct |
9 ms |
8192 KB |
Output is correct |
9 |
Correct |
9 ms |
8192 KB |
Output is correct |
10 |
Correct |
9 ms |
8192 KB |
Output is correct |
11 |
Correct |
8 ms |
8192 KB |
Output is correct |
12 |
Correct |
8 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8192 KB |
Output is correct |
3 |
Correct |
9 ms |
8192 KB |
Output is correct |
4 |
Correct |
9 ms |
8192 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
8 ms |
8192 KB |
Output is correct |
7 |
Correct |
9 ms |
8192 KB |
Output is correct |
8 |
Correct |
9 ms |
8192 KB |
Output is correct |
9 |
Correct |
9 ms |
8192 KB |
Output is correct |
10 |
Correct |
9 ms |
8192 KB |
Output is correct |
11 |
Correct |
8 ms |
8192 KB |
Output is correct |
12 |
Correct |
8 ms |
8192 KB |
Output is correct |
13 |
Correct |
8 ms |
8192 KB |
Output is correct |
14 |
Correct |
8 ms |
8192 KB |
Output is correct |
15 |
Correct |
8 ms |
8164 KB |
Output is correct |
16 |
Correct |
8 ms |
8192 KB |
Output is correct |
17 |
Correct |
8 ms |
8192 KB |
Output is correct |
18 |
Correct |
8 ms |
8192 KB |
Output is correct |
19 |
Correct |
8 ms |
8192 KB |
Output is correct |
20 |
Correct |
8 ms |
8192 KB |
Output is correct |
21 |
Correct |
8 ms |
8192 KB |
Output is correct |
22 |
Correct |
8 ms |
8192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8192 KB |
Output is correct |
3 |
Correct |
9 ms |
8192 KB |
Output is correct |
4 |
Correct |
9 ms |
8192 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
8 ms |
8192 KB |
Output is correct |
7 |
Correct |
9 ms |
8192 KB |
Output is correct |
8 |
Correct |
9 ms |
8192 KB |
Output is correct |
9 |
Correct |
9 ms |
8192 KB |
Output is correct |
10 |
Correct |
9 ms |
8192 KB |
Output is correct |
11 |
Correct |
8 ms |
8192 KB |
Output is correct |
12 |
Correct |
8 ms |
8192 KB |
Output is correct |
13 |
Correct |
8 ms |
8192 KB |
Output is correct |
14 |
Correct |
8 ms |
8192 KB |
Output is correct |
15 |
Correct |
8 ms |
8164 KB |
Output is correct |
16 |
Correct |
8 ms |
8192 KB |
Output is correct |
17 |
Correct |
8 ms |
8192 KB |
Output is correct |
18 |
Correct |
8 ms |
8192 KB |
Output is correct |
19 |
Correct |
8 ms |
8192 KB |
Output is correct |
20 |
Correct |
8 ms |
8192 KB |
Output is correct |
21 |
Correct |
8 ms |
8192 KB |
Output is correct |
22 |
Correct |
8 ms |
8192 KB |
Output is correct |
23 |
Correct |
12 ms |
8448 KB |
Output is correct |
24 |
Correct |
12 ms |
8448 KB |
Output is correct |
25 |
Correct |
12 ms |
8448 KB |
Output is correct |
26 |
Correct |
16 ms |
8704 KB |
Output is correct |
27 |
Correct |
16 ms |
8704 KB |
Output is correct |
28 |
Correct |
17 ms |
8960 KB |
Output is correct |
29 |
Correct |
15 ms |
8832 KB |
Output is correct |
30 |
Correct |
15 ms |
8832 KB |
Output is correct |
31 |
Correct |
17 ms |
9472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
8192 KB |
Output is correct |
2 |
Correct |
9 ms |
8192 KB |
Output is correct |
3 |
Correct |
9 ms |
8192 KB |
Output is correct |
4 |
Correct |
9 ms |
8192 KB |
Output is correct |
5 |
Correct |
8 ms |
8192 KB |
Output is correct |
6 |
Correct |
8 ms |
8192 KB |
Output is correct |
7 |
Correct |
9 ms |
8192 KB |
Output is correct |
8 |
Correct |
9 ms |
8192 KB |
Output is correct |
9 |
Correct |
9 ms |
8192 KB |
Output is correct |
10 |
Correct |
9 ms |
8192 KB |
Output is correct |
11 |
Correct |
8 ms |
8192 KB |
Output is correct |
12 |
Correct |
8 ms |
8192 KB |
Output is correct |
13 |
Correct |
8 ms |
8192 KB |
Output is correct |
14 |
Correct |
8 ms |
8192 KB |
Output is correct |
15 |
Correct |
8 ms |
8164 KB |
Output is correct |
16 |
Correct |
8 ms |
8192 KB |
Output is correct |
17 |
Correct |
8 ms |
8192 KB |
Output is correct |
18 |
Correct |
8 ms |
8192 KB |
Output is correct |
19 |
Correct |
8 ms |
8192 KB |
Output is correct |
20 |
Correct |
8 ms |
8192 KB |
Output is correct |
21 |
Correct |
8 ms |
8192 KB |
Output is correct |
22 |
Correct |
8 ms |
8192 KB |
Output is correct |
23 |
Correct |
12 ms |
8448 KB |
Output is correct |
24 |
Correct |
12 ms |
8448 KB |
Output is correct |
25 |
Correct |
12 ms |
8448 KB |
Output is correct |
26 |
Correct |
16 ms |
8704 KB |
Output is correct |
27 |
Correct |
16 ms |
8704 KB |
Output is correct |
28 |
Correct |
17 ms |
8960 KB |
Output is correct |
29 |
Correct |
15 ms |
8832 KB |
Output is correct |
30 |
Correct |
15 ms |
8832 KB |
Output is correct |
31 |
Correct |
17 ms |
9472 KB |
Output is correct |
32 |
Correct |
69 ms |
10812 KB |
Output is correct |
33 |
Correct |
79 ms |
10872 KB |
Output is correct |
34 |
Correct |
57 ms |
10872 KB |
Output is correct |
35 |
Correct |
332 ms |
18936 KB |
Output is correct |
36 |
Correct |
347 ms |
18904 KB |
Output is correct |
37 |
Correct |
357 ms |
18848 KB |
Output is correct |
38 |
Correct |
272 ms |
20712 KB |
Output is correct |
39 |
Correct |
286 ms |
21464 KB |
Output is correct |
40 |
Correct |
288 ms |
20928 KB |
Output is correct |
41 |
Correct |
363 ms |
26224 KB |
Output is correct |