#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int dp[MAXN][2];
vector<PII>adj[MAXN];
void dfs(int nd,int pr=-1,int w_p=-1){
dp[nd][0]=0;int mx=-INF,mx1=-INF;
for(int i=0;i<int(adj[nd].size());i++){
int to=adj[nd][i].ff;
int w=adj[nd][i].ss;
if(to==pr)continue;
dfs(to,nd,w);
w+=dp[to][0]-dp[to][1];
dp[nd][0]+=dp[to][1];
if(mx<w) mx1=mx,mx=w;
else umax(mx1,w);
}
if(~pr)dp[nd][1]=dp[nd][0]+max(0,mx+w_p);
else dp[nd][0]+=max(0,mx+mx1);
}
int main(){
//freopen("file.in", "r", stdin);
int n;
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
adj[u].pb(mp(v,w));
adj[v].pb(mp(u,w));
}int ans=0;
vector<int>roots;
for(int i=1;i<=n;i++)roots.pb(i);
random_shuffle(all(roots));
for(int i=0;i<n;i++){
if(clock()/CLOCKS_PER_SEC>0.99)break;
dfs(roots[i]);
umax(ans,dp[roots[i]][0]);
}
printf("%d\n",ans);
return 0;
}
Compilation message
beads.cpp: In function 'int main()':
beads.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
beads.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%d%d%d",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2648 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2648 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2656 KB |
Output is correct |
16 |
Correct |
3 ms |
2656 KB |
Output is correct |
17 |
Correct |
3 ms |
2636 KB |
Output is correct |
18 |
Correct |
3 ms |
2648 KB |
Output is correct |
19 |
Correct |
4 ms |
2636 KB |
Output is correct |
20 |
Correct |
3 ms |
2648 KB |
Output is correct |
21 |
Correct |
3 ms |
2636 KB |
Output is correct |
22 |
Correct |
3 ms |
2656 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2648 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2656 KB |
Output is correct |
16 |
Correct |
3 ms |
2656 KB |
Output is correct |
17 |
Correct |
3 ms |
2636 KB |
Output is correct |
18 |
Correct |
3 ms |
2648 KB |
Output is correct |
19 |
Correct |
4 ms |
2636 KB |
Output is correct |
20 |
Correct |
3 ms |
2648 KB |
Output is correct |
21 |
Correct |
3 ms |
2636 KB |
Output is correct |
22 |
Correct |
3 ms |
2656 KB |
Output is correct |
23 |
Correct |
767 ms |
2980 KB |
Output is correct |
24 |
Correct |
722 ms |
2892 KB |
Output is correct |
25 |
Correct |
768 ms |
2996 KB |
Output is correct |
26 |
Execution timed out |
1000 ms |
3336 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
2 ms |
2648 KB |
Output is correct |
3 |
Correct |
2 ms |
2636 KB |
Output is correct |
4 |
Correct |
2 ms |
2636 KB |
Output is correct |
5 |
Correct |
2 ms |
2636 KB |
Output is correct |
6 |
Correct |
2 ms |
2636 KB |
Output is correct |
7 |
Correct |
2 ms |
2636 KB |
Output is correct |
8 |
Correct |
2 ms |
2636 KB |
Output is correct |
9 |
Correct |
2 ms |
2636 KB |
Output is correct |
10 |
Correct |
3 ms |
2636 KB |
Output is correct |
11 |
Correct |
3 ms |
2636 KB |
Output is correct |
12 |
Correct |
2 ms |
2636 KB |
Output is correct |
13 |
Correct |
2 ms |
2636 KB |
Output is correct |
14 |
Correct |
2 ms |
2636 KB |
Output is correct |
15 |
Correct |
2 ms |
2656 KB |
Output is correct |
16 |
Correct |
3 ms |
2656 KB |
Output is correct |
17 |
Correct |
3 ms |
2636 KB |
Output is correct |
18 |
Correct |
3 ms |
2648 KB |
Output is correct |
19 |
Correct |
4 ms |
2636 KB |
Output is correct |
20 |
Correct |
3 ms |
2648 KB |
Output is correct |
21 |
Correct |
3 ms |
2636 KB |
Output is correct |
22 |
Correct |
3 ms |
2656 KB |
Output is correct |
23 |
Correct |
767 ms |
2980 KB |
Output is correct |
24 |
Correct |
722 ms |
2892 KB |
Output is correct |
25 |
Correct |
768 ms |
2996 KB |
Output is correct |
26 |
Execution timed out |
1000 ms |
3336 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |