트리의 지름

https://www.acmicpc.net/problem/1967

1967번: 트리의 지름

 

#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
class Pair{
public:
    int to, value;
    Pair(int to, int value) {
        this->to = to;
        this->value = value;
    }
    bool operator <(Pair& p) {
        return this->to < p.to;
    }
};
int n,ans;
vector<Pair> tree[10001];
bool d[10001];
 
struct info {
    int from, value, parent;
    info(int from, int value, int parent) {
        this->from = from;
        this->value = value;
        this->parent = parent;
    }
};
 
void bfs(int x) {
    queue<info> q;
    d[x] = true;
    vector<int> v[10001];
    for (int i = 0; i < tree[x].size(); i++) {
        q.push(info( tree[x][i].to, tree[x][i].value, tree[x][i].to));
        d[tree[x][i].to] = true;
    }
    
    while (!q.empty()) {
        int from = q.front().from; int value = q.front().value;
        int parent = q.front().parent;
        q.pop();
        if (tree[from].size() == 1) {
            if (v[parent].size() == 0) v[parent].push_back(value);
            if (v[parent][0] < value)
            {
                v[parent].pop_back();
                v[parent].push_back(value);
            }
            continue;
        }
        for (int i = 0; i < tree[from].size(); i++) {
            if (d[tree[from][i].to] == false) {
                d[tree[from][i].to] = true;
                q.push(info( tree[from][i].to, value + tree[from][i].value,parent ));
            }
        }
    }
 
    vector<int> sum;
    for (int i = 0; i < tree[x].size(); i++) {
        sum.push_back(v[tree[x][i].to][0]);
    }
 
    sort(sum.begin(), sum.end());
    if (ans < sum[sum.size() - 1] + sum[sum.size() - 2])
        ans = sum[sum.size() - 1] + sum[sum.size() - 2];
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    int ending = 0;
    for (int i = 0; i < n-1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        tree[a].push_back(Pair(b,c));
        tree[b].push_back(Pair(a, c));
        if (a > ending) ending = a;
    }
    /*for (int i = 1; i <= ending; i++) {
        sort(tree[i].begin(), tree[i].end());
    }*/
    for (int i = 1; i <= n; i++) {
        if (tree[i].size() > 1) {
            bfs(i);
            memset(d, false, sizeof(d));
        }
    }
    cout << ans << '\n';
    
    return 0;
}

트리지름문제

그냥 모든 노드들어가서 최대 노드 길이 하나하나 다해줬는데 사실 그럴필요는없다.