이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 200005
#define int long long
#define fi first
#define se second
typedef pair<int, int> ii;
int n, dp[3][N], res = 0, wi[N], mm[N];
vector<ii> adj[N];
bool cmp(int& a, int& b){
return a > b;
}
void dfs(int u, int p){
int d1 = 0, d2 = 0, ma = -1e15;
vector<int> tmp;
for (auto x : adj[u]){
int v = x.fi, w = x.se;
if (v == p) continue;
dfs(v, u);
if (dp[0][v] != 0){
dp[1][u] += max(dp[0][v] + w, dp[1][v]);
}
else dp[1][u] += dp[1][v];
if (dp[0][v] != 0){
dp[0][u] += dp[0][v] + w;
ma = max(ma, dp[1][v] - dp[0][v]);
}
else ma = max(ma, dp[1][v] + w);
wi[v] = w;
}
dp[0][u] += ma;
mm[u] = ma;
//cout << u << " " << dp[0][u] << " " << dp[1][u] << "\n";
}
void ud(int p0, int p1, int v){
int cst = p1;
if (p0 != 0) cst = max(cst, p0 + wi[v]);
dp[1][v]+= cst;
dp[0][v] -= mm[v];
if (p0 != 0){
dp[0][v] += p0 + wi[v];
mm[v] = max(mm[v], p1 - p0);
}
else mm[v] = max(mm[v], p1 + wi[v]);
dp[0][v] += mm[v];
}
void rr(int u, int p, int p0, int p1){
res = max(res, dp[1][u]);
int siz = adj[u].size() - (p != 0);
vector<int> pre(siz + 2, 0), suf(siz + 2, 0), mpre(siz + 2, 0), msuf(siz + 2, 0);
mpre[0] = -1e15, msuf[siz + 1] = -1e15;
if (p != 0){
if (p0 != 0){
pre[0] += p0 + wi[u];
mpre[0] = p1 - p0;
}
else mpre[0] = p1 + wi[u];
}
int pos = 0;
for (auto x : adj[u]){
int v = x.fi, w = x.se;
if (v == p) continue;
pos++;
pre[pos] = pre[pos - 1];
mpre[pos] = mpre[pos - 1];
if (dp[0][v] > 0){
pre[pos] += dp[0][v] + w;
mpre[pos] = max(mpre[pos], dp[1][v] - dp[0][v]);
}
else mpre[pos] = max(mpre[pos], dp[1][v] + w);
}
pos = siz + 1;
for (int i = adj[u].size() - 1; i >= 0; i--){
int v = adj[u][i].fi, w = adj[u][i].se;
if (v == p) continue;
pos--;
suf[pos] = suf[pos + 1];
msuf[pos] = msuf[pos + 1];
if (dp[0][v] > 0){
suf[pos] += dp[0][v] + w;
msuf[pos] = max(msuf[pos], dp[1][v] - dp[0][v]);
}
else msuf[pos] = max(msuf[pos], dp[1][v] + w);
}
pos = 0;
for (auto x : adj[u]){
int v = x.fi, w = x.se;
if (v == p) continue;
int cst = dp[1][v];
pos++;
if (dp[0][v] != 0) cst = max(cst, dp[0][v] + w);
int p1 = dp[1][u] - cst;
int p0 = pre[pos - 1] + suf[pos + 1] + max(mpre[pos - 1], msuf[pos + 1]);
//if (u ==1 && v == 3) cout <<"check : " << pre[pos - 1] << " " << suf[pos + 1] << " " << max(mpre[pos - 1], msuf[pos + 1]) << "\n";
ud(p0, p1, v);
rr(v, u, p0, p1);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n;
for (int i = 1; i <= n - 1; i++){
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
int root = 1;
dfs(root, 0);
rr(root, 0, 0, 0);
cout << res;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
beads.cpp: In function 'void dfs(long long int, long long int)':
beads.cpp:19:6: warning: unused variable 'd1' [-Wunused-variable]
19 | int d1 = 0, d2 = 0, ma = -1e15;
| ^~
beads.cpp:19:14: warning: unused variable 'd2' [-Wunused-variable]
19 | int d1 = 0, d2 = 0, ma = -1e15;
| ^~
# | 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... |