You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
reacted with thumbs up emoji reacted with thumbs down emoji reacted with laugh emoji reacted with hooray emoji reacted with confused emoji reacted with heart emoji reacted with rocket emoji reacted with eyes emoji
Uh oh!
There was an error while loading. Please reload this page.
문제 링크
https://www.acmicpc.net/problem/15681
문제 조건
가중치와 방향성이 없는 임의의 루트 트리가 주어졌을 때, 아래 쿼리를 답하라
" 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력하라 "
아이디어
첫번째 방법 - 시간 초과
제일 처음 생각한 방법은 트리의 정보를 인접리스트에 담은 후 요청하는 쿼리마다 DFS나 BFS로 서브쿼리의 수를 구하는 방식이다.
하지만 쿼리의 최대 수는 10^5이고, 서브 쿼리를 구하는 최대 시간은 10^5으로 총 O(10^10)이라서 1초 안에 풀 수 없는 방법이다.
두번째 방법
미리 모든 정점을 각각 루트로 하는 서브트리에서의 정점의 수를 빠르게 구해두면 쿼리마다 해당 배열의 값을 반환만 해주면 되므로 시간 안에 풀이가 가능할 것이다.
시간 복잡도
DFS를 도는데 걸리는 시간은 O(10^5)이므로 시간 안 풀이가 가능하다.
구현
All reactions