1167번 트리의 지름

똑같은 문제 풀이 : http://hsdevelopment.tistory.com/90

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

84번 째 줄은 삭제해야 한다. 

문제에서

먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다.

문제에서 각 하나의 정점에 대한 정보들이 '차례대로 모두' 주어지므로, 굳이 84번 째 줄을 작성할 필요는 없다

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0;
 
vector<pair<int, int> > v[100001]; // child, weight
 
bool visit[100001] = { false, };
 
int V = 0, W = 0;
 
int sum[100001] = { 0, };;
 
void BFS(int start)
{
    memset(visit, false, sizeof(visit));
 
    queue<int> q;
 
    q.push(start);
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int here = q.front();
 
            q.pop();
 
            if (visit[here]) continue;
 
            visit[here] = true;
 
            for (int i = 0; i < v[here].size(); i++)
            {
                int next_vertex = v[here].at(i).first;
 
                if (!visit[next_vertex])
                {
                    q.push(next_vertex);
 
                    sum[next_vertex] += v[here].at(i).second + sum[here];
 
                    if (W < sum[next_vertex])
                    {
                        W = sum[next_vertex];
                        V = next_vertex;
                    }
                }
            }
        }
    }
}
 
int main(void)
{
    int parent = 0, child = 0, weight = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &parent);
 
        while (1)
        {
            scanf("%d", &child);
 
            if (child == -1) break;
 
            scanf("%d", &weight);
 
            v[parent].push_back({ child, weight });
            //v[child].push_back({ parent, weight });
        }
    }
 
    BFS(1);
 
    memset(sum, 0, sizeof(sum));
 
    
 
    BFS(V);
 
 
    printf("%d\n", W);
    
    return 0;
}