Tree 썸네일형 리스트형 BOJ 17399 트리의 외심 https://www.acmicpc.net/problem/17399 17399번: 트리의 외심 첫 번째 줄에 정점의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 이 트리는 1번 정점, 2번 정점, ..., N번 정점으로 구성된다. 두 번째 줄부터 N번째 줄까지, 트리의 간선 정보를 의미하는 두 자연수 X, Y가 www.acmicpc.net 일단 각 쿼리에 대해 트리에서 최소 공통 조상(Lowest Common Ancestor)을 log n에 구할 수 있어야 한다. 알고리즘 두 정점 a와 b에 대해, 두 정점의 가운데에 위치한 정점 x를 찾는다. a와 b 거리가 짝수여야 한다. 그렇지 않으면 가운데에 위치한 정점을 정의할 수 없다. 단계 1에서 찾은 정점 x로부터 정점 c까지의 거리를 구한다. x.. 더보기 External Path Length IPL(Internal Path Length): Binary Tree의 각 노드의 depth의 합 EPL(Extend Path Length): Extended Binary Tree에 새로 추가된 노드들의 depth의 합 위 그림에서 왼쪽의 트리가 원래의 Binary Tree이고 오른쪽의 트리가 Extended Binary Tree이다. 오른쪽의 트리에서 동그라미로 그려진 노드가 Internal이고 네모로 그려진 노드가 External노드, 즉 원래의 Tree를 Extended Binary Tree로 만들기 위해 추가된 노드들이다. IPL은 동그라미로 그려진 노드들의 depth의 합으로 위의 그림에서 그 값이 11이 된다. EPL은 네모로 그려진 노드들의 depth의 합으로 위의 그림에서 그 값은 25이다.. 더보기 Party at Hali-Bula http://acm.pku.edu.cn/JudgeOnline/problem?id=3342 Description Dear Contestant, I'm going to have a party at my villa at Hali-Bula to celebrate my retirement from BCM. I wish I could invite all my co-workers, but imagine how an employee can enjoy a party when he finds his boss among the guests! So, I decide not to invite both an employee and his/her boss. The organizational hierarchy at BCM is su.. 더보기 이전 1 다음