#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000000000000
int n;
ll da[200005],db[200005],dc[200005],dd[200005];
vector<P>g[200005];
void up(ll &x,ll y){
if(x<y)x=y;
}
void dfs(int v,int p,ll pc){
ll sa=0,sm=-INF,acc=-INF,acd=-INF,dm=-INF;
for(int i=0;i<g[v].size();i++){
int u=g[v][i].F;
ll c=g[v][i].S;
if(u==p)continue;
dfs(u,v,c);
sa+=da[u];
up(sm,-da[u]+db[u]);
up(dm,acc-da[u]+c+dd[u]);
up(dm,acd-da[u]+c+dc[u]);
up(acc,-da[u]+c+dc[u]);
up(acd,-da[u]+c+dd[u]);
}
up(dc[v],sa);
up(dd[v],sa);
up(dd[v],sa+sm);
up(da[v],sa+acc+pc);
up(db[v],sa+acd+pc);
up(dd[v],sa+dm);
up(da[v],dc[v]);
up(db[v],dd[v]);
}
int main(void){
scanf("%d",&n);
for(int i=0;i<n-1;i++){
ll a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
g[--a].PB(P(--b,c));
g[b].PB(P(a,c));
}
for(int i=0;i<n;i++)da[i]=-INF,db[i]=-INF,dc[i]=-INF,dd[i]=-INF;
dfs(0,-1,-INF);
printf("%lld\n",dd[0]);
}
Compilation message
beads.cpp: In function 'void dfs(int, int, ll)':
beads.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++){
~^~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:44:8: 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 |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
6 ms |
5120 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
5120 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
6 ms |
5120 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
5120 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5040 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
5 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
6 ms |
5120 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
5120 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5040 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
5 ms |
5120 KB |
Output is correct |
23 |
Correct |
8 ms |
5504 KB |
Output is correct |
24 |
Correct |
8 ms |
5376 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
11 ms |
5888 KB |
Output is correct |
27 |
Correct |
11 ms |
5888 KB |
Output is correct |
28 |
Correct |
10 ms |
5884 KB |
Output is correct |
29 |
Correct |
11 ms |
5760 KB |
Output is correct |
30 |
Correct |
10 ms |
5888 KB |
Output is correct |
31 |
Correct |
12 ms |
6296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
5120 KB |
Output is correct |
2 |
Correct |
6 ms |
5120 KB |
Output is correct |
3 |
Correct |
5 ms |
4992 KB |
Output is correct |
4 |
Correct |
6 ms |
5120 KB |
Output is correct |
5 |
Correct |
5 ms |
4992 KB |
Output is correct |
6 |
Correct |
6 ms |
4992 KB |
Output is correct |
7 |
Correct |
6 ms |
4992 KB |
Output is correct |
8 |
Correct |
6 ms |
4992 KB |
Output is correct |
9 |
Correct |
6 ms |
4992 KB |
Output is correct |
10 |
Correct |
6 ms |
4992 KB |
Output is correct |
11 |
Correct |
5 ms |
4992 KB |
Output is correct |
12 |
Correct |
6 ms |
4992 KB |
Output is correct |
13 |
Correct |
6 ms |
4992 KB |
Output is correct |
14 |
Correct |
5 ms |
4992 KB |
Output is correct |
15 |
Correct |
6 ms |
4992 KB |
Output is correct |
16 |
Correct |
6 ms |
5040 KB |
Output is correct |
17 |
Correct |
5 ms |
4992 KB |
Output is correct |
18 |
Correct |
6 ms |
4992 KB |
Output is correct |
19 |
Correct |
6 ms |
5120 KB |
Output is correct |
20 |
Correct |
6 ms |
4992 KB |
Output is correct |
21 |
Correct |
6 ms |
5120 KB |
Output is correct |
22 |
Correct |
5 ms |
5120 KB |
Output is correct |
23 |
Correct |
8 ms |
5504 KB |
Output is correct |
24 |
Correct |
8 ms |
5376 KB |
Output is correct |
25 |
Correct |
8 ms |
5376 KB |
Output is correct |
26 |
Correct |
11 ms |
5888 KB |
Output is correct |
27 |
Correct |
11 ms |
5888 KB |
Output is correct |
28 |
Correct |
10 ms |
5884 KB |
Output is correct |
29 |
Correct |
11 ms |
5760 KB |
Output is correct |
30 |
Correct |
10 ms |
5888 KB |
Output is correct |
31 |
Correct |
12 ms |
6296 KB |
Output is correct |
32 |
Correct |
43 ms |
9212 KB |
Output is correct |
33 |
Correct |
44 ms |
9208 KB |
Output is correct |
34 |
Correct |
47 ms |
9252 KB |
Output is correct |
35 |
Correct |
228 ms |
21496 KB |
Output is correct |
36 |
Correct |
241 ms |
21624 KB |
Output is correct |
37 |
Correct |
238 ms |
21628 KB |
Output is correct |
38 |
Correct |
161 ms |
20732 KB |
Output is correct |
39 |
Correct |
152 ms |
20700 KB |
Output is correct |
40 |
Correct |
153 ms |
20696 KB |
Output is correct |
41 |
Correct |
218 ms |
26212 KB |
Output is correct |