#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
#include <unordered_map>
#define pb push_back
using namespace std;
typedef pair<int,int> pp;
struct pt{int u,c;};
typedef vector<int> vec;
typedef vector<pt> vec2;
typedef vector<vec> mat;
typedef vector<vec2> graph;
unordered_map<int,int> ID[200010];
mat dp[2];
graph path;
int N;
int root;
void input(){
scanf("%d",&N);
path.assign(N+1,vec2());
dp[0].assign(N+1,vec());
dp[1].assign(N+1,vec());
int x,y,z;
for(int i=0;i<N-1;i++){
scanf("%d%d%d",&x,&y,&z);
ID[x][y]=path[x].size();
ID[y][x]=path[y].size();
path[x].pb(pt{y,z});
path[y].pb(pt{x,z});
dp[0][x].pb(-1);dp[1][x].pb(-1);
dp[0][y].pb(-1);dp[1][y].pb(-1);
}
for(int i=1;i<=N;i++){
ID[i][i]=path[i].size();
dp[0][i].pb(-1);
dp[1][i].pb(-1);
}
}
void process(int v,int p,int mode){
int sz=path[v].size();
int cnt=sz-(v!=root);
int& ret=dp[mode][v][ID[v][p]];
ret=0;
if(cnt==0){
if(mode==1)ret = -1e9;
return;
}
vec a;
for(int i=0;i<sz;i++){
int u=path[v][i].u;
int c=path[v][i].c;
int id=ID[u][v];
if(p==u)continue;
int z = max(dp[0][u][id],dp[1][u][id]+c);
ret+=z;
if(mode==1){
a.pb(dp[0][u][id]+c-z);
}
}
if(mode==1){ // mode==1
ret+=*max_element(a.begin(),a.end());
}
}
void dfs(int v,int p,int mode){
int& ret=dp[mode][v][ID[v][p]];
if(~ret)return;
for(int i=0;i<path[v].size();i++){
int u=path[v][i].u;
if(u==p)continue;
dfs(u,v,0);
dfs(u,v,1);
}
process(v,p,mode);
}
void PS(){
int ans=0;
for(int i=1;i<=N;i++){
root=i;
dfs(i,i,0);
ans=max(ans,dp[0][i][ID[i][i]]);
}
printf("%d\n",ans);
}
int main(){
input();
PS();
return 0;
}
Compilation message
beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<path[v].size();i++){
~^~~~~~~~~~~~~~~
beads.cpp: In function 'void input()':
beads.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
~~~~~^~~~~~~~~
beads.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d",&x,&y,&z);
~~~~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11264 KB |
Output is correct |
2 |
Correct |
11 ms |
11264 KB |
Output is correct |
3 |
Correct |
11 ms |
11264 KB |
Output is correct |
4 |
Correct |
11 ms |
11264 KB |
Output is correct |
5 |
Correct |
12 ms |
11264 KB |
Output is correct |
6 |
Correct |
10 ms |
11264 KB |
Output is correct |
7 |
Correct |
11 ms |
11264 KB |
Output is correct |
8 |
Correct |
11 ms |
11236 KB |
Output is correct |
9 |
Correct |
11 ms |
11264 KB |
Output is correct |
10 |
Correct |
11 ms |
11264 KB |
Output is correct |
11 |
Correct |
11 ms |
11264 KB |
Output is correct |
12 |
Correct |
11 ms |
11264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11264 KB |
Output is correct |
2 |
Correct |
11 ms |
11264 KB |
Output is correct |
3 |
Correct |
11 ms |
11264 KB |
Output is correct |
4 |
Correct |
11 ms |
11264 KB |
Output is correct |
5 |
Correct |
12 ms |
11264 KB |
Output is correct |
6 |
Correct |
10 ms |
11264 KB |
Output is correct |
7 |
Correct |
11 ms |
11264 KB |
Output is correct |
8 |
Correct |
11 ms |
11236 KB |
Output is correct |
9 |
Correct |
11 ms |
11264 KB |
Output is correct |
10 |
Correct |
11 ms |
11264 KB |
Output is correct |
11 |
Correct |
11 ms |
11264 KB |
Output is correct |
12 |
Correct |
11 ms |
11264 KB |
Output is correct |
13 |
Correct |
12 ms |
11264 KB |
Output is correct |
14 |
Correct |
13 ms |
11264 KB |
Output is correct |
15 |
Correct |
12 ms |
11328 KB |
Output is correct |
16 |
Correct |
13 ms |
11392 KB |
Output is correct |
17 |
Correct |
13 ms |
11392 KB |
Output is correct |
18 |
Correct |
13 ms |
11392 KB |
Output is correct |
19 |
Correct |
17 ms |
11392 KB |
Output is correct |
20 |
Correct |
14 ms |
11264 KB |
Output is correct |
21 |
Correct |
16 ms |
11392 KB |
Output is correct |
22 |
Correct |
13 ms |
11392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11264 KB |
Output is correct |
2 |
Correct |
11 ms |
11264 KB |
Output is correct |
3 |
Correct |
11 ms |
11264 KB |
Output is correct |
4 |
Correct |
11 ms |
11264 KB |
Output is correct |
5 |
Correct |
12 ms |
11264 KB |
Output is correct |
6 |
Correct |
10 ms |
11264 KB |
Output is correct |
7 |
Correct |
11 ms |
11264 KB |
Output is correct |
8 |
Correct |
11 ms |
11236 KB |
Output is correct |
9 |
Correct |
11 ms |
11264 KB |
Output is correct |
10 |
Correct |
11 ms |
11264 KB |
Output is correct |
11 |
Correct |
11 ms |
11264 KB |
Output is correct |
12 |
Correct |
11 ms |
11264 KB |
Output is correct |
13 |
Correct |
12 ms |
11264 KB |
Output is correct |
14 |
Correct |
13 ms |
11264 KB |
Output is correct |
15 |
Correct |
12 ms |
11328 KB |
Output is correct |
16 |
Correct |
13 ms |
11392 KB |
Output is correct |
17 |
Correct |
13 ms |
11392 KB |
Output is correct |
18 |
Correct |
13 ms |
11392 KB |
Output is correct |
19 |
Correct |
17 ms |
11392 KB |
Output is correct |
20 |
Correct |
14 ms |
11264 KB |
Output is correct |
21 |
Correct |
16 ms |
11392 KB |
Output is correct |
22 |
Correct |
13 ms |
11392 KB |
Output is correct |
23 |
Correct |
28 ms |
12800 KB |
Output is correct |
24 |
Correct |
29 ms |
12800 KB |
Output is correct |
25 |
Correct |
31 ms |
12888 KB |
Output is correct |
26 |
Correct |
46 ms |
14464 KB |
Output is correct |
27 |
Correct |
54 ms |
14456 KB |
Output is correct |
28 |
Execution timed out |
1086 ms |
14584 KB |
Time limit exceeded |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
11264 KB |
Output is correct |
2 |
Correct |
11 ms |
11264 KB |
Output is correct |
3 |
Correct |
11 ms |
11264 KB |
Output is correct |
4 |
Correct |
11 ms |
11264 KB |
Output is correct |
5 |
Correct |
12 ms |
11264 KB |
Output is correct |
6 |
Correct |
10 ms |
11264 KB |
Output is correct |
7 |
Correct |
11 ms |
11264 KB |
Output is correct |
8 |
Correct |
11 ms |
11236 KB |
Output is correct |
9 |
Correct |
11 ms |
11264 KB |
Output is correct |
10 |
Correct |
11 ms |
11264 KB |
Output is correct |
11 |
Correct |
11 ms |
11264 KB |
Output is correct |
12 |
Correct |
11 ms |
11264 KB |
Output is correct |
13 |
Correct |
12 ms |
11264 KB |
Output is correct |
14 |
Correct |
13 ms |
11264 KB |
Output is correct |
15 |
Correct |
12 ms |
11328 KB |
Output is correct |
16 |
Correct |
13 ms |
11392 KB |
Output is correct |
17 |
Correct |
13 ms |
11392 KB |
Output is correct |
18 |
Correct |
13 ms |
11392 KB |
Output is correct |
19 |
Correct |
17 ms |
11392 KB |
Output is correct |
20 |
Correct |
14 ms |
11264 KB |
Output is correct |
21 |
Correct |
16 ms |
11392 KB |
Output is correct |
22 |
Correct |
13 ms |
11392 KB |
Output is correct |
23 |
Correct |
28 ms |
12800 KB |
Output is correct |
24 |
Correct |
29 ms |
12800 KB |
Output is correct |
25 |
Correct |
31 ms |
12888 KB |
Output is correct |
26 |
Correct |
46 ms |
14464 KB |
Output is correct |
27 |
Correct |
54 ms |
14456 KB |
Output is correct |
28 |
Execution timed out |
1086 ms |
14584 KB |
Time limit exceeded |
29 |
Halted |
0 ms |
0 KB |
- |