AcWing 1073. 나무의 중심 (트 리 DP) 문제 풀이

제목 전송 문
제목 설명
나무 한 그루 를 정 하고 나무 에는 n 개의 결점 (번호 1 ~ n) 과 n - 1 개의 무 방향 변 이 포함 되 어 있 으 며 각 변 에 하나의 가중치 가 있 습 니 다.
나무 에서 다른 결점 의 가장 먼 거리 에서 가장 가 까 운 점 을 찾 아 보 세 요.
입력 형식
첫 줄 은 정수 n 을 포함한다.
다음 n - 1 줄 은 각 줄 에 세 개의 정수 ai, bi, ci 를 포함 하고 점 ai 와 bi 사이 에 하나의 가중치 가 ci 인 변 이 존재 한 다 는 것 을 나타 낸다.
출력 형식
원 하 는 점 에서 트 리 의 다른 노드 까지 의 가장 먼 거 리 를 나타 내 는 정 수 를 출력 합 니 다.
데이터 범위
1≤n≤10000 1≤ai,bi≤n −105≤ci≤105
입력 예시:
5 2 1 1 3 2 1 4 3 1 5 1 1
출력 예시:
2
문제 풀이:
트 리 DP: dfs 두 번, 처음으로 u 를 노드 로 하고 d1 과 d2 로 아래로 가 는 가장 긴 길 과 차장 길 을 기록 하 며 p1 p2 로 가장 긴 길 과 차장 길이 어느 노드 에서 왔 는 지 기록 하고 마지막 으로 u 를 노드 로 내 려 가 는 가장 먼 거리 와 위로 가 는 가장 먼 거리의 최소 값 을 취한 다.

#include
#include
using namespace std;
const int N = 10010;
int h[N], e[N * 2], w[N * 2], ne[N * 2], idx;
// d1   d2       i               
//up             
//p1   p2                     
int d1[N], d2[N], up[N], p1[N], p2[N];
int ans;
void add(int a, int b, int c)
{
     
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dfs_d(int u, int father)//   
{
     
    if(h[u] == -1) return 0;
    d1[u] = d2[u] = -1e9;
    for(int i = h[u]; i != -1; i = ne[i]){
     
        int j = e[i];
        if(j == father)continue;
        int d = dfs_d(j, u) + w[i];
        if(d >= d1[u]){
     

            d2[u] = d1[u];
            d1[u] = d;
            p2[u] = p1[u], p1[u] = j;
        }
        else if(d > d2[u]){
     
            d2[u] = d;
            p2[u] = j;
        }
    }
    if(d1[u] == -1e9)d1[u] = d2[u] = 0; //          
    return d1[u];
} 
void dfs_u(int u, int father)//   
{
     
    for(int i = h[u]; i != -1; i = ne[i]){
     
        int j = e[i];
        if(j == father)continue;
        if(p1[u] == j)up[j] = max(up[u], d2[u]) + w[i];  //      ,     up[u];
        else up[j] = max(up[u], d1[u]) + w[i];  //      ，   up[u];
        dfs_u(j, u);
    }
}
int main()
{
     
    int n;
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 0; i < n - 1; i++){
     
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    ans = 1e9;
    dfs_d(1, -1);//   
    dfs_u(1, -1);
    int res = 1e9;
    for(int i = 1; i <= n; i++)res = min(res, max(d1[i], up[i]));
    cout << res << endl;
    return 0;
}