SRM 682 Div.1

300 : tonyjjw랑 나랑 푼 방법이 거의 같은데 뭔가 이상하다. 우선 중복간선은 존재하지 않는다고 입력 조건에 있음. 각각의 간선을 잘라보면서 트리의 지름을 구하듯이 어떤 점에서 가장 먼 점을 찾고 거기서 또 가장 먼 점을 찾음. 지름의 길이가 5 이상되면 답이 되는 체인이 존재한다고 했서 맞았음. O(n^2).

tonyjjw를 통해서 ainu7님의 정해를 들으니 a-b-c-d-e가 있으면, a-b와 d-e를 전처리로 n^2에 구한다. 이후 b와 d 사이에 존재하는 c 후보들에 대해 a와 e랑 다른 걸 찾으면 된다고 한다. 전처리를 잘하면 전체 O(n^2)에 수행된다.

450 : 간선 하나(중복 간선은 간선 하나로 전처리) 달린 정점들 개수(C)를 카운팅하고 다음에 n-C-1 출력하니까 예제가 다 나왔다. 친구랑 밥 먹기로 해서 이렇게 짧게 5분도 생각 못한 걸 제출하고 나갔더니 역시나 첼린지 당함...

1-2-3-1 사이클이고 3-4인 가지가 있는 그래프인 경우 1하고 2만 합치면 3을 capital로 지정하면 됨. 그런데 내 프로그램은 C=1이니까 2를 출력함. 사이클에서 자식이 안 딸린 애가 하나라도 있으면 걔도 남길 수 있어서 하나 더 준다. 이걸 고려하면 맞음ㅋㅋ 많이 아깝다....