# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
580930 | 2022-06-22T06:31:38 Z | 조영욱(#8362) | 구슬과 끈 (APIO14_beads) | C++17 | 6 ms | 9684 KB |
#include <bits/stdc++.h> using namespace std; int n; typedef pair<int,int> P; vector<P> adj[200001]; long long dp[200001][2]; vector<P> son[200001]; const long long nnn=-1e16; const long long nn=-1e12-7; int rr; void dfs(int v,int prev) { dp[v][0]=0; dp[v][1]=0; long long mx=0; for(int i=0;i<adj[v].size();i++) { P nt=adj[v][i]; if (nt.first!=prev) { dfs(nt.first,v); dp[v][0]+=max(dp[nt.first][0],dp[nt.first][1]+nt.second); dp[v][1]+=max(dp[nt.first][0],dp[nt.first][1]+nt.second); mx=max(mx,dp[nt.first][0]+nt.second-max(dp[nt.first][0],dp[nt.first][1]+nt.second)); } } dp[v][1]+=mx; } int main(void) { scanf("%d",&n); for(int i=1;i<n;i++) { int u,v,w; scanf("%d %d %d",&u,&v,&w); u--; v--; adj[u].push_back(P(v,w)); adj[v].push_back(P(u,w)); } long long ret=0; for(int r=0;r<n;r++) { rr=r; dfs(r,-1); ret=max(ret,dp[r][0]); } printf("%lld",ret); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 9684 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 9684 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 9684 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 9684 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |