15940_네트워크 연결

ucpc c번

구현이 극혐이긴한데 또 생각보다 별거 없기도 하다.
내가 https://www.acmicpc.net/problem/13016 문제를 푼거랑 비슷한 방식의 트리dp를 사용하면 된다.
ucpc 당시에는 원래 그래프에서 트리의 지름을 하나 구하고 트리의 지름에 속하지 않는 노드를 가지고 
다시 sub지름을 구해서 잘 연결해준다. 로 접근했었는데 
이러면 트리에 같은 크기를 갖는 지름이 여러개 있을 경우 어떤 지름을 원래 지름으로 선택하느냐에 따라서 
최대값이 이상하게 나올 수 있다. 
그래서 정해는 모든 간선을 잘라본다. 이다.
근데 모든 간선을 자를때마다 subtree의 지름과 그 subtree를 제외한 나머지 트리의 지름을 구해서 연결하면 O(n^2)이 된다.
본선당시에 다들 n^2까진 생각했을 것이다.

나는 처음에 dfs를 돌리면서 
각 노드를 root로 하는 subtree의 지름값, 그 노드에서 leaf로 가는 최장거리 3개, 
그 노드의 자식들의 지름값 중 최대값 2개를 각각 저장해주었다.
(정해 슬라이드를 보면 최장거리 3개랑 subtree의 지름값만 저장해서 잘 하던데 나는 생각이 안나서 조금 더 저장해버륌)
각 노드를 root로 하는 subtree의 지름값은 
(그 노드에서 leaf로 가는 최장거리 2개의 합), (자식들의 지름값 중 최대값 1개) 중에 max값으로 결정된다.

그리고 dfs2를 돌리면서 이제 정답을 찾아주는데
각 노드에서 그 노드의 자식으로 가는 경로를 끊었을 때
전체 트리에서 자기를 루트로 하는  subtree를 뺀 tree의 지름값,
전체 트리에서 자기를 루트로 하는 subtree를 뺀 tree에서 자기까지 오는 최장경로 + 자기에서 (자식 a로 가는 subtree를 빼고) leaf까지 가는 최장경로,
자기 자식의 지름값,
이 3개 중에 최대값이 전체 트리 - 자기 자식을 루트로 하는 subtree를 뺀 tree에서의 지름값이 된다.
그러면 이 값을 가지고 다시 구해주고 구해주고 구해주면 됨

내가 한 말이 이해가 안되면 정해 슬라이드 그림과 함께 보면 더 잘 이해됨.

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <cmath>
using namespace std;
typedef long long ll;
int N;
ll a, b, c, res;
vector<vector<pair<int, ll>>> adj;
pair<ll, int> maxx[200001][4];
//나부터 가장 먼 leaf까지의 값 1, 2, 3개
pair<ll, int> maxdia[200001][2];
//내 자식들을 root로 하는 subtree의 지름 중 가장 큰 값 두개
ll subdia[200001];
//int p[200001];
 
pair<ll, ll> dfs(int cur, int par) {
    pair<ll, ll> ret = { 0, 0 };
    //지름, 최대길이
    for (auto next : adj[cur]) {
        if (next.first == par) continue;
    //    p[next.first] = cur;
        auto tmp = dfs(next.first, cur);
 
        //최대 길이 갱신
        if (maxx[cur][1].first < tmp.second + next.second || maxx[cur][1].second == 0) {
            maxx[cur][3] = maxx[cur][2];
            maxx[cur][2] = maxx[cur][1];
            maxx[cur][1] = { tmp.second + next.second, next.first };
        }
        else if (maxx[cur][2].first < tmp.second + next.second || maxx[cur][2].second == 0) {
            maxx[cur][3] = maxx[cur][2];
            maxx[cur][2] = { tmp.second + next.second, next.first };
        }
        else if (maxx[cur][3].first < tmp.second + next.second || maxx[cur][3].second == 0) {
            maxx[cur][3] = { tmp.second + next.second, next.first };
        }
 
        //최대 지름 갱신
        if (maxdia[cur][0].first < tmp.first || maxdia[cur][0].second == 0) {
            maxdia[cur][1] = maxdia[cur][0];
            maxdia[cur][0] = { tmp.first, next.first };
        }
        else if (maxdia[cur][1].first < tmp.first || maxdia[cur][1].second == 0) {
            maxdia[cur][1] = { tmp.first, next.first };
        }
    }
 
    subdia[cur] = max(maxx[cur][1].first + maxx[cur][2].first, maxdia[cur][0].first );
 
    ret = { subdia[cur] , maxx[cur][1].first };
    return ret;
}
 
void dfs2(int cur, int par, ll pmaxdia, ll pmaxlen) {
 
    for (auto next : adj[cur]) {
        if (next.first == par) continue;
        ll tmp1, tmp2;
        //tmp1 - cur의 subtree에서 next를 제외하고 지름의 최대값
        //tmp2 - cur의 subtree에서 next를 제외하고 leaf까지의 최대값
        //pmaxdia - cur의 부모의 지름의 값
 
        if (maxx[cur][1].second == next.first) {
            tmp1 = maxx[cur][2].first + maxx[cur][3].first;
            tmp2 = maxx[cur][2].first;
        }
        else if (maxx[cur][2].second == next.first) {
            tmp1 = maxx[cur][1].first + maxx[cur][3].first;
            tmp2 = maxx[cur][1].first;
        }
        else {
            tmp1 = maxx[cur][1].first + maxx[cur][2].first;
            tmp2 = maxx[cur][1].first;
        }
 
        if (maxdia[cur][0].second == next.first) {
            tmp1 = max(tmp1, maxdia[cur][1].first);
        }
        else {
            tmp1 = max(tmp1, maxdia[cur][0].first);
        }
 
        res = max(res, next.second + subdia[next.first] + max(pmaxdia, max(tmp1, tmp2 + pmaxlen)) );
        dfs2(next.first, cur, max(pmaxdia, max(tmp1, tmp2 + pmaxlen)) , max(tmp2, pmaxlen) + next.second);
    }
}
 
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N;
    adj.resize(N + 1);
 
    for (int i = 0; i < N-1; ++i) {
        cin >> a >> b >> c;
        adj[a].push_back({ b, c });
        adj[b].push_back({ a, c });
    }
 
    
    dfs(1, 0); //기본적인 트리값 구성
    dfs2(1, 0, 0, 0);
 
    cout << res;
    return 0;
}