cho.sh견우와 직녀
아직 제출이 없습니다시간 제한1초메모리 제한1024 MB문제
견우는 정점의 개수가 N인 무향 가중치 트리 E에 살고 있고, 직녀는 정점의 개수가 M인 무향 가중치 트리 W에 살고 있다.
두 사람은 각자 다른 트리에 살고 있으므로 만날 수 없다... 슬픔에 빠진 두 사람을 위해 옥황상제는 매년 7월 7일이 되면 오작교를 이어 두 사람이 만날 수 있게 해주려고 한다.
오작교는 길이가 1인 간선이며 옥황상제는 두 사람이 만나기 쉽도록 E의 모든 정점과 W의 모든 정점 사이의 거리의 합이 최소가 되도록 이어주려고 한다.
견우와 직녀를 위해 7월 7일이 되면 어떤 정점에서 오작교가 이어지는지 알려주도록 하자!
입력
첫째 줄에 E의 정점 개수 N(1≤N≤100,000)이 주어진다.
다음 N−1개의 줄에 걸쳐 E의 간선이 a b c(1≤a,b≤N;1≤c≤104)와 같은 형식으로 주어진다. 이는 E의 a번 정점과 b번 정점 사이의 거리가 c라는 것을 뜻한다.
다음 줄에 W의 정점 개수 M(1≤M≤100,000)이 주어진다.
다음 M−1개의 줄에 걸쳐 W의 간선이 a b c(1≤a,b≤M;1≤c≤104)와 같은 형식으로 주어진다. 이는 W의 a번 정점과 b번 정점 사이의 거리가 c라는 것을 뜻한다.
주어지는 입력은 모두 정수다.
출력
첫째 줄에 오작교가 이어지게 되는 E의 정점 번호와 W의 정점 번호를 공백을 사이에 두고 차례대로 출력한다. 가능한 경우가 여러 가지라면 그 중 아무거나 출력한다.
둘째 줄에 오작교가 이어진 후 E의 모든 정점과 W의 모든 정점 사이의 거리의 합을 출력한다.
힌트
E의 모든 정점과 W의 모든 정점 사이의 거리의 합을 수학적으로 정의하면 다음과 같다.
\[ \sum_{u \in E} \sum_{v \in W} dist(u, v) \]