이 문제는 서브테스크를 긁고 최적화를 할 방법을 모르겠어서 풀이를 봤다. 풀이가 신기하고 좋은 문제라고 생각해서 풀이를 올려본다. https://www.acmicpc.net/problem/25402 25402번: 트리와 쿼리 첫 번째 줄부터 $Q$개의 줄에 걸쳐, 각 질의에 대한 답을 출력한다. 이 중 $i$ ($1 ≤ i ≤ Q$)번째 줄에는 $i$번째 질의에서 주어진 $S$에 대하여, $S$의 연결 강도를 출력한다. www.acmicpc.net 이 문제를 요악하자면 트리를 S라는 집합의 정점들로만 한정지었을때, 생기는 각 컴포넌트들의 연결 되어있는 노드의 개수를 구하면 된다. 연결 개수는 컴포넌트의 노드 개수를 n이라 했을때, nC2가 된다. 나이브하게 매 쿼리마다 dfs를 돌리며 컴포넌트의 개수를 ..