#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
ll n, ans, par[200005], dt[200005][2];
ll missing[200005], sum[200005];
bool vis[200005][2];
pair<ll, ll> mx[200005][2];
vector<ll> cg[200005], cv[200005];
void update (ll cur, ll idx, ll val);
ll getsum(ll cur, ll prev);
ll solve(ll cur, ll prev, ll val);
void update (ll cur, ll idx, ll val) {
if(mx[cur][0].second<val) {
mx[cur][1] = mx[cur][0];
mx[cur][0] = {idx, val};
}
else if(mx[cur][1].second<val) {
mx[cur][1] = {idx, val};
}
}
ll getsum (ll cur, ll prev) {
if(missing[cur]) {
if(~missing[cur]) {
if(missing[cur] == prev) return sum[cur];
for(int i=0;i<cg[cur].size();i++) {
if(cg[cur][i] != missing[cur]) continue;
sum[cur] += solve(cg[cur][i], cur, cv[cur][i]);
update(cur, cg[cur][i], getsum(cg[cur][i],cur)-solve(cg[cur][i],cur,cv[cur][i])+cv[cur][i]);
}
missing[cur] = -1;
}
return sum[cur]-solve(prev, cur, 0);
}
else {
for(int i=0;i<cg[cur].size();i++) {
if(cg[cur][i] == prev) continue;
sum[cur] += solve(cg[cur][i], cur, cv[cur][i]);
}
for(int i=0;i<cg[cur].size();i++) {
if(cg[cur][i] == prev) continue;
ll tmp = getsum(cg[cur][i],cur)-solve(cg[cur][i],cur,cv[cur][i])+cv[cur][i];
update(cur, cg[cur][i], tmp);
}
missing[cur] = prev;
return sum[cur];
}
}
ll solve (ll cur, ll prev, ll val) {
int flag = 0, piv;
if(par[cur] != prev) {piv = prev; flag = 1;}
else piv = cur;
if(vis[piv][flag]) return dt[piv][flag];
vis[piv][flag] = true;
ll def = getsum(cur,prev), ret = def;
ret = max(ret, def + (prev==mx[cur][0].first?mx[cur][1].second:mx[cur][0].second) + val);
dt[piv][flag] = ret;
return ret;
}
void precalc (ll cur, ll prev) {
par[cur] = prev;
for(int i=0;i<cg[cur].size();i++) {
if(cg[cur][i] == prev) continue;
precalc(cg[cur][i], cur);
}
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<n;i++) {
ll A, B, C;
scanf("%lld%lld%lld",&A,&B,&C);
cg[A].push_back(B); cv[A].push_back(C);
cg[B].push_back(A); cv[B].push_back(C);
}
for(int i=1;i<=n;i++) {
for(int j=0;j<2;j++) {
mx[i][j] = {0, -inf};
}
}
precalc(1, -1);
for(int i=1;i<=n;i++) {
ll ret = 0;
for(int j=0;j<cg[i].size();j++) {
ret += solve(cg[i][j],i,cv[i][j]);
}
ans = max(ans, ret);
}
printf("%lld",ans);
}
Compilation message
beads.cpp: In function 'll getsum(ll, ll)':
beads.cpp:30:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cg[cur].size();i++) {
~^~~~~~~~~~~~~~~
beads.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cg[cur].size();i++) {
~^~~~~~~~~~~~~~~
beads.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cg[cur].size();i++) {
~^~~~~~~~~~~~~~~
beads.cpp: In function 'void precalc(ll, ll)':
beads.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cg[cur].size();i++) {
~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<cg[i].size();j++) {
~^~~~~~~~~~~~~
beads.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
beads.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",&A,&B,&C);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9720 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
10 ms |
9720 KB |
Output is correct |
6 |
Correct |
10 ms |
9720 KB |
Output is correct |
7 |
Correct |
10 ms |
9720 KB |
Output is correct |
8 |
Correct |
10 ms |
9800 KB |
Output is correct |
9 |
Correct |
10 ms |
9720 KB |
Output is correct |
10 |
Correct |
12 ms |
9720 KB |
Output is correct |
11 |
Correct |
10 ms |
9724 KB |
Output is correct |
12 |
Correct |
11 ms |
9720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9720 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
10 ms |
9720 KB |
Output is correct |
6 |
Correct |
10 ms |
9720 KB |
Output is correct |
7 |
Correct |
10 ms |
9720 KB |
Output is correct |
8 |
Correct |
10 ms |
9800 KB |
Output is correct |
9 |
Correct |
10 ms |
9720 KB |
Output is correct |
10 |
Correct |
12 ms |
9720 KB |
Output is correct |
11 |
Correct |
10 ms |
9724 KB |
Output is correct |
12 |
Correct |
11 ms |
9720 KB |
Output is correct |
13 |
Correct |
10 ms |
9848 KB |
Output is correct |
14 |
Correct |
10 ms |
9720 KB |
Output is correct |
15 |
Correct |
10 ms |
9720 KB |
Output is correct |
16 |
Correct |
10 ms |
9848 KB |
Output is correct |
17 |
Correct |
10 ms |
9792 KB |
Output is correct |
18 |
Correct |
11 ms |
9848 KB |
Output is correct |
19 |
Correct |
10 ms |
9720 KB |
Output is correct |
20 |
Correct |
10 ms |
9720 KB |
Output is correct |
21 |
Correct |
10 ms |
9720 KB |
Output is correct |
22 |
Correct |
10 ms |
9720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9720 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
10 ms |
9720 KB |
Output is correct |
6 |
Correct |
10 ms |
9720 KB |
Output is correct |
7 |
Correct |
10 ms |
9720 KB |
Output is correct |
8 |
Correct |
10 ms |
9800 KB |
Output is correct |
9 |
Correct |
10 ms |
9720 KB |
Output is correct |
10 |
Correct |
12 ms |
9720 KB |
Output is correct |
11 |
Correct |
10 ms |
9724 KB |
Output is correct |
12 |
Correct |
11 ms |
9720 KB |
Output is correct |
13 |
Correct |
10 ms |
9848 KB |
Output is correct |
14 |
Correct |
10 ms |
9720 KB |
Output is correct |
15 |
Correct |
10 ms |
9720 KB |
Output is correct |
16 |
Correct |
10 ms |
9848 KB |
Output is correct |
17 |
Correct |
10 ms |
9792 KB |
Output is correct |
18 |
Correct |
11 ms |
9848 KB |
Output is correct |
19 |
Correct |
10 ms |
9720 KB |
Output is correct |
20 |
Correct |
10 ms |
9720 KB |
Output is correct |
21 |
Correct |
10 ms |
9720 KB |
Output is correct |
22 |
Correct |
10 ms |
9720 KB |
Output is correct |
23 |
Correct |
15 ms |
10488 KB |
Output is correct |
24 |
Correct |
15 ms |
10488 KB |
Output is correct |
25 |
Correct |
15 ms |
10488 KB |
Output is correct |
26 |
Correct |
20 ms |
11384 KB |
Output is correct |
27 |
Correct |
21 ms |
11356 KB |
Output is correct |
28 |
Correct |
18 ms |
11512 KB |
Output is correct |
29 |
Correct |
18 ms |
11372 KB |
Output is correct |
30 |
Correct |
19 ms |
11384 KB |
Output is correct |
31 |
Correct |
21 ms |
11896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
9720 KB |
Output is correct |
2 |
Correct |
10 ms |
9720 KB |
Output is correct |
3 |
Correct |
10 ms |
9720 KB |
Output is correct |
4 |
Correct |
10 ms |
9720 KB |
Output is correct |
5 |
Correct |
10 ms |
9720 KB |
Output is correct |
6 |
Correct |
10 ms |
9720 KB |
Output is correct |
7 |
Correct |
10 ms |
9720 KB |
Output is correct |
8 |
Correct |
10 ms |
9800 KB |
Output is correct |
9 |
Correct |
10 ms |
9720 KB |
Output is correct |
10 |
Correct |
12 ms |
9720 KB |
Output is correct |
11 |
Correct |
10 ms |
9724 KB |
Output is correct |
12 |
Correct |
11 ms |
9720 KB |
Output is correct |
13 |
Correct |
10 ms |
9848 KB |
Output is correct |
14 |
Correct |
10 ms |
9720 KB |
Output is correct |
15 |
Correct |
10 ms |
9720 KB |
Output is correct |
16 |
Correct |
10 ms |
9848 KB |
Output is correct |
17 |
Correct |
10 ms |
9792 KB |
Output is correct |
18 |
Correct |
11 ms |
9848 KB |
Output is correct |
19 |
Correct |
10 ms |
9720 KB |
Output is correct |
20 |
Correct |
10 ms |
9720 KB |
Output is correct |
21 |
Correct |
10 ms |
9720 KB |
Output is correct |
22 |
Correct |
10 ms |
9720 KB |
Output is correct |
23 |
Correct |
15 ms |
10488 KB |
Output is correct |
24 |
Correct |
15 ms |
10488 KB |
Output is correct |
25 |
Correct |
15 ms |
10488 KB |
Output is correct |
26 |
Correct |
20 ms |
11384 KB |
Output is correct |
27 |
Correct |
21 ms |
11356 KB |
Output is correct |
28 |
Correct |
18 ms |
11512 KB |
Output is correct |
29 |
Correct |
18 ms |
11372 KB |
Output is correct |
30 |
Correct |
19 ms |
11384 KB |
Output is correct |
31 |
Correct |
21 ms |
11896 KB |
Output is correct |
32 |
Correct |
77 ms |
17828 KB |
Output is correct |
33 |
Correct |
70 ms |
17912 KB |
Output is correct |
34 |
Correct |
76 ms |
17912 KB |
Output is correct |
35 |
Correct |
455 ms |
42744 KB |
Output is correct |
36 |
Correct |
431 ms |
42688 KB |
Output is correct |
37 |
Correct |
449 ms |
42808 KB |
Output is correct |
38 |
Correct |
287 ms |
43480 KB |
Output is correct |
39 |
Correct |
289 ms |
41916 KB |
Output is correct |
40 |
Correct |
304 ms |
43216 KB |
Output is correct |
41 |
Correct |
435 ms |
47708 KB |
Output is correct |