| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 18463 | tlwpdus | 구슬과 끈 (APIO14_beads) | C++98 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
#include<algorithm>
#define MAXN 200010
#define MAXM 200010
using namespace std;
typedef long long ll;
int n;
int nxt[MAXM*2], st[MAXN], en[MAXM*2], wei[MAXM*2];
ll dyn[MAXN][4];
void dfs(int here, int p, int uew) {
int i;
ll cnt = 0, sum0123 = 0, sum02 = 0, m0[2]={-2e9,-2e9}, m1[2]={-2e9,-2e9}, t0, t1;
for (i=st[here];i!=-1;i=nxt[i]) {
int there = en[i];
if (there==p) continue;
dfs(there,here,wei[i]);
cnt++;
int v = max(dyn[there][0],dyn[there][2]);
sum0123 += max(max(dyn[there][0],dyn[there][1]),max(dyn[there][2],dyn[there][3]));
sum02 += v;
int val0 = dyn[there][0]-v+wei[i];
int val1 = dyn[there][1]-v+wei[i];
if (m0[0]<val0) m0[1]=m0[0],m0[0]=val0,t0=there;
else if (m0[1]<val0) m0[1]=val0;
if (m1[0]<val1) m1[1]=m1[0],m1[0]=val1,t1=there;
else if (m1[1]<val1) m1[1]=val1;
}
dyn[here][0] = sum0123;
if (cnt>1) dyn[here][1] = sum02+max(m0[0]+m0[1],(t0!=t1)?(m0[0]+m1[0]):(max(m0[1]+m1[0],m0[0]+m1[1])));
if (cnt>0) dyn[here][2] = sum02+m0[0]+uew;
if (cnt>0) dyn[here][3] = sum02+m1[0]+uew;
}
void process() {
dfs(0,-1,0);
printf("%lld\n",max(dyn[0][0],dyn[0][1]));
}
int ptr = 0;
void add_edge(int u, int v, int w) {
nxt[ptr] = st[u];
wei[ptr] = w;
en[ptr] = v;
st[u] = ptr++;
nxt[ptr] = st[v];
wei[ptr] = w;
en[ptr] = u;
st[v] = ptr++;
}
void input() {
int i;
scanf("%d",&n);
for (i=0;i<n;i++) st[i] = -1;
for (i=0;i<n-1;i++) {
int a, b, w;
scanf("%d %d %d",&a,&b,&w);
add_edge(--a,--b,w);
}
}
int main() {
//freopen("input.txt","r",stdin);
input();
process();
return 0;
}