글 읽기 - 트리의 지름 질문입니다.

now1413 8년 전 0

예제랑 보기 만들어서 해봤는데 잘 나오는데 틀렸습니다 나오네요

어디가 잘못된건지 모르겠습니다 ㅜㅜ 알려주세요

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
vector<vector<pair<long long, long long>>> tree;
long long mmax=0;
long long n,x,y,z;
long long treee(long long a);
int main(){
    cin >> n;
    tree.resize(n+1);
    for(int i=0;i<n;i++){
        cin >> x ;
        while(1){
            cin >> y ;
            if(y==-1)
                break;
            cin >> z ;
            if(tree[y].size()==0){
                tree[x].push_back({y,z});
            }
        }
    }
    for(int i=1;i<=n;i++){
        treee(1);
    }
    cout << mmax << endl;
    return 0;
}
long long treee(long long a){
    pair<long long, long long> total = {0,0};
    for(int i=0;i<tree[a].size();i++){
        long long dis = treee(tree[a][i].first) + tree[a][i].second;
        if(dis > total.first)  swap(total.first, total.second), total.first = dis;
        else if(dis > total.second) total.second = dis;
    }
    mmax = max(total.first + total.second , mmax);
    return total.first;
}

baekjoon 8년 전 8

트리의 지름을 구하는 방법은 다음과 같습니다.

먼저, 임의의 정점 A에서 모든 정점까지의 거리를 구합니다. 그 때, 가장 거리가 먼 정점을 B라고 합니다.

이제, B에서 모든 정점까지의 거리를 구합니다. 여기서 구한 가장 거리가 먼 거리가 트리의 지름입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

트리의 지름 질문입니다.

now1413 8년 전 0

baekjoon 8년 전 8

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말