이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct edge{
int v,w;
edge(int v=0,int w=0): v(v), w(w) {}
};
int n;
vector <edge> G[200005];
int dp[200005][5];
inline int val1(int pos,int w){
return dp[pos][0] + w;
}
inline int val02(int pos,int w){
return max(dp[pos][0], dp[pos][2] + w);
}
void dfs(int u,int p){
for(int i=0;i<G[u].size();i++){
int v = G[u][i].v;
if (v == p) continue;
dfs(v,u);
}
// dp[i][0]
dp[u][0] = 0;
for(int i=0;i<G[u].size();i++){
int v = G[u][i].v;
if (v == p) continue;
dp[u][0] += val02(v,G[u][i].w);
}
// dp[i][1]
int fi02=0,se02=0,fiva02=-(int)1e9, seva02=-(int)1e9;
for(int i=0;i<G[u].size();i++){
int v = G[u][i].v;
int w = G[u][i].w;
if (v == p) continue;
if (val1(v,w) - val02(v,w) >= val1(fi02,fiva02) - val02(fi02,fiva02))
se02 = fi02,
seva02 = fiva02,
fi02 = v,
fiva02 = w;
else if (val1(v,w) - val02(v,w) >= val1(se02,seva02) - val02(se02,seva02))
se02 = v,
seva02 = w;
}
dp[u][1] = - (int) 1e9;
for(int i=0;i<G[u].size();i++){
int v = G[u][i].v;
int w = G[u][i].w;
if (v == p) continue;
dp[u][1] = max(dp[u][1], dp[u][0] - val02(v,w) + dp[v][1]);
dp[u][1] = max(dp[u][1], dp[u][0] - val02(v,w) + dp[v][3] + w);
if (v != fi02)//cout <<"k\n",
dp[u][1] = max(dp[u][1], dp[u][0] - val02(v,w) + dp[v][1] + w - val02(fi02,fiva02) + dp[fi02][0] + fiva02);
else if (se02)
dp[u][1] = max(dp[u][1], dp[u][0] - val02(v,w) + dp[v][1] + w - val02(se02,seva02) + dp[se02][0] + seva02);
}
if (se02){
dp[u][1] = max(dp[u][1], dp[u][0] - val02(fi02,fiva02) - val02(se02,seva02) + val1(fi02,fiva02) + val1(se02,seva02));
}
// dp[i][2]
dp[u][2] = -(int)1e9;
for(int i=0;i<G[u].size();i++){
int v = G[u][i].v;
int w = G[u][i].w;
if (v == p) continue;
dp[u][2] = max(dp[u][2], dp[u][0] - val02(v,w) + dp[v][0] + G[u][i].w);
}
// dp[i][3]
dp[u][3] = -(int)1e9;
for(int i=0;i<G[u].size();i++){
int v = G[u][i].v;
int w = G[u][i].w;
if (v == p) continue;
dp[u][3] = max(dp[u][3], dp[u][0] - val02(v,w) + dp[v][1] + G[u][i].w);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int x,y,w;
scanf("%d %d %d",&x,&y,&w);
G[x].push_back(edge(y,w));
G[y].push_back(edge(x,w));
}
dfs(1,1);
cout << max(dp[1][0], dp[1][1]) << endl;
//for(int i=1;i<=n;i++)
// cout << "I " << i << ' ' << dp[i][0] <<' ' << dp[i][1] << ' ' << dp[i][2] << ' ' << dp[i][3] << endl;
}
/*
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
10
4 10 5
1 10 7
3 10 10
3 9 10
2 3 5
3 8 9
7 10 3
5 8 9
4 6 6
10
2 3 7
6 9 7
2 10 6
4 9 2
2 8 5
1 6 1
6 7 10
6 8 9
2 5 6
*/
컴파일 시 표준 에러 (stderr) 메시지
beads.cpp: In function 'void dfs(int, int)':
beads.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[u].size();i++){
~^~~~~~~~~~~~
beads.cpp:24:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[u].size();i++){
~^~~~~~~~~~~~
beads.cpp:31:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[u].size();i++){
~^~~~~~~~~~~~
beads.cpp:45:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[u].size();i++){
~^~~~~~~~~~~~
beads.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[u].size();i++){
~^~~~~~~~~~~~
beads.cpp:69:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<G[u].size();i++){
~^~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
beads.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&x,&y,&w);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |