1부터 N까지 N 개의 정점으로 이루어진 트리가 있다.

i번째 간선은 서로 다른 두 정점 A, B 를 잇는다. (1 ≤ i ≤ N - 1)

N 개의 정점 중 몇 개를 골라, 그 고른 정점들을 S = \{s_1, s_2, ···, s_K\}라고 하자.

또한 s_i = v를 만족하는 i (1 ≤ i ≤ K)가 존재할 때, 정점 v가 S에 속한다고 부르자.

S에 속하는 서로 다른 두 정점 u, v에 대하여, S에 속하는 정점만을 이용하여 트리 위에서 u, v 사이를 오갈 수 있다면,

"u와 v는 S 위에서 연결되어 있다"고 하자.

예를 들어, 아래와 같은 트리를 생각하자. (N = 7)

만일, K = 6, S = \{1, 2, 3, 4, 5, 6\}라면, "1과 2", "3과 5", "4와 6"은 각각 서로 S 위에서 연결되어 있다.

그러나, "1과 6", "2와 7"은 각각 서로 S 위에서 연결되어 있지 않다.

다음 조건을 모두 만족하는 정점쌍 (u, v)의 개수를 S의 연결 강도라고 하자.

고른 정점들 S가 주어질 때, S의 연결 강도를 계산하는 프로그램을 작성하라.

여러분은 이러한 질의 Q개에 대하여 모두 답해야 한다.

트리와 쿼리 timer 6초 memory 256MB

트리와 쿼리 6초 256MB