핵심 마을 거리 합 질의
다이아몬드 III의견: 0
\(N\)개의 마을이 \(N-1\)개의 양방향 도로로 연결된 트리 형태의 나라가 있다. 각 도로에는 양의 정수 길이가 있다. 두 마을 사이의 거리는 둘을 잇는 유일한 경로의 길이 합이다.
\(Q\)개의 질의가 주어진다. 각 질의는 핵심 마을의 집합 \(S\)로 주어진다. 각 질의마다 \(S\)에 속한 서로 다른 두 마을의 모든 쌍에 대해 거리의 총합을 구하여라. 즉 \(\sum_{u
모든 질의의 \(|S|\) 합이 매우 클 수 있으므로, 질의마다 트리 전체를 순회하는 풀이는 통과할 수 없다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le w \le 10^6\)
\(1 \le a, b \le N\)
\(1 \le k \le N\), 모든 질의의 \(k\) 합 \(\le 200{,}000\)
첫 줄에 마을 수 \(N\)과 질의 수 \(Q\)가 주어진다.
다음 \(N-1\)개의 줄에 각각 세 정수 \(a\), \(b\), \(w\)가 주어지며 마을 \(a\)와 \(b\)를 잇는 길이 \(w\)의 도로를 의미한다.
이어서 \(Q\)개의 줄에 각 질의가 주어진다. 각 줄은 핵심 마을의 수 \(k\)로 시작하고, 그 뒤에 서로 다른 마을 번호 \(k\)개가 주어진다.
각 질의에 대해 핵심 마을 쌍 거리의 총합을 한 줄에 하나씩 출력한다.
4 2
1 2 3
1 3 1
3 4 1
3 2 3 4
2 1 4
10
2거리: (2,3)=4,(2,4)=5,(3,4)=1 이므로 첫 질의 합은 10. 둘째 질의 (1,4)=2 이므로 2.
5 2
2 1 2
3 2 2
4 3 2
5 4 2
3 1 3 5
2 2 4
16
4길이 2짜리 사슬 1-2-3-4-5. 첫 질의 {1,3,5}: (1,3)=4,(1,5)=8,(3,5)=4 합 16. 둘째 질의 {2,4}: (2,4)=4 이므로 4.
riseoj 작성
출처 Original
평가 및 의견
핵심 마을 거리 합 질의
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
핵심 마을 거리 합 질의