반응형 백준 25638번1 백준 25638번 : 트리와 경로 개수 쿼리 (C++) 백준 25638번 q개의 쿼리에 대해 정점 u를 지나는 경로의 개수를 구하는 문제이다. 정점 u에 대해서 다음과 같이 2개의 트리로 쪼개 진다고 가정해보자. 트리 x에대해 빨간점의 개수를 red[x], 파란점의 개수를 blue[x]라고 정의할때, 경로의 개수는 red[1]*blue[2] + blue[1]*red[2]개이다. 따라서 각각의 트리에 대해 red[x], blue[x]를 구하는 것이 핵심이라고 할 수 있다. 그러나 모든 쿼리마다 각각의 트리의 red[x], blue[x]를 계산하면 시간 초과가 날 것이 뻔하다. 보다 효율적인 방법을 생각해보자. 우선 풀이의 편의성을 위해 루트를 1로 설정하겠다. 그리고 임이의 정점u를 아래 그림으로 나타내었다. r[x], b[x]를 아래와 같이 정의해주자 r[x.. 2023. 5. 5. 이전 1 다음 반응형
