Update 1240.cpp

encrypted-def · web-flow · commit bfe598e3b22f · 2022-09-06T23:47:52.000+09:00
diff --git a/0x19/solutions/1240.cpp b/0x19/solutions/1240.cpp
@@ -41,7 +41,8 @@ int main(void) {
 }
 /*
 트리 구조여서 간선의 수는 N-1이니 bfs 한 번의 시간복잡도는 O(N)입니다. 
-NM = 1,000,000이기 때문에 각 쿼리에 대해서 BFS 또는 DFS를 수행해도 무방합니다.
+NM = 1,000,000이기 때문에 각 쿼리에 대해서 BFS 또는 DFS를 수행해도 O(NM)으로 무방합니다.
 N <= 1000이고 M <= 5,000,000과 같이 M이 훨씬 더 컸다면 미리 bfs를 N번 돌려 모든 N^2개의 거리를
-다 계산해 별도의 테이블에 저장해둔 후 답을 바로바로 출력하는 풀이도 가능합니다.
+O(N^2)에 다 계산해 별도의 테이블에 저장해둔 후 답을 바로바로 출력하는 O(N^2+M) 풀이도 가능합니다.
+만약 간선에 가중치가 있었다면 트리dp를 이용해 O(N^2+M)에 해결할 수 있습니다.
 */
