#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=200010;
const int mxM=7300000;
const int mxK=100001;
const int MOD=1000000007;
const ll INF=9223372036854775807;
int N;
vector <pii> v[mxN];
vector <pii> adj[mxN];
ll par[mxN];
ll dp1[mxN], dp2[mxN];
typedef struct cmp1{
bool operator()(ll a, ll b)
{
return a>b;
}
}cmp1;
void dfs0(int now, int pre)
{
for(pii nxt : v[now]) if(nxt.fir!=pre)
{
dfs0(nxt.fir, now);
adj[now].push_back(nxt);
par[nxt.fir]=nxt.sec;
}
}
void dfs1(int now)
{
priority_queue <ll, vector<ll>, cmp1> pq;
ll sum1=0;
for(pii nxt : adj[now])
{
dfs1(nxt.fir);
}
for(pii nxt : adj[now])
{
//printf("dp1[%d]=%lld, dp2[%d]=%lld\n", nxt.fir, dp1[nxt.fir], nxt.fir, dp2[nxt.fir]);
sum1+=dp1[nxt.fir];
pq.push(dp2[nxt.fir]+nxt.sec-dp1[nxt.fir]);
}
while(pq.size()>2) pq.pop();
ll tmp1, tmp2;
if(adj[now].empty())
{
dp2[now]=0;
dp1[now]=0;
return;
}
if(adj[now].size()==1)
{
dp2[now]=sum1;
dp1[now]=max(dp2[now], sum1+par[now]+pq.top());
return;
}
tmp1=pq.top();
pq.pop();
tmp2=pq.top();
pq.pop();
//printf("tmp1=%lld, tmp2=%lld\n", tmp1, tmp2);
dp2[now]=sum1+max((ll)0, tmp1+tmp2);
dp1[now]=max(dp2[now], sum1+par[now]+tmp2);
}
int main()
{
gibon
cin >> N;
for(int i=1;i<N;i++)
{
int a, b, c;
cin >> a >> b >> c;
v[a].push_back({b, c});
v[b].push_back({a, c});
}
dfs0(N, -1);
dfs1(N);
cout << dp2[N];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
6 ms |
9728 KB |
Output is correct |
4 |
Correct |
6 ms |
9688 KB |
Output is correct |
5 |
Correct |
6 ms |
9676 KB |
Output is correct |
6 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
6 ms |
9728 KB |
Output is correct |
4 |
Correct |
6 ms |
9688 KB |
Output is correct |
5 |
Correct |
6 ms |
9676 KB |
Output is correct |
6 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
6 ms |
9728 KB |
Output is correct |
4 |
Correct |
6 ms |
9688 KB |
Output is correct |
5 |
Correct |
6 ms |
9676 KB |
Output is correct |
6 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
9676 KB |
Output is correct |
2 |
Correct |
6 ms |
9684 KB |
Output is correct |
3 |
Correct |
6 ms |
9728 KB |
Output is correct |
4 |
Correct |
6 ms |
9688 KB |
Output is correct |
5 |
Correct |
6 ms |
9676 KB |
Output is correct |
6 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |