205301 백준(BOJ) 20530 양분(Python) DFS 문제. 일반적인 트리에서는 u번 정점에서 v번 정점으로 가는 단순 경로가 1개 존재한다. 그러나 트리에 하나의 간선이 추가되면, 이 때는 이야기가 달라진다. 트리에 하나의 간선이 추가됨으로써 그래프 내에는 반드시 하나의 사이클이 발생한다. 사이클이 발생하게 되면 해당 사이클을 기점으로 단순 경로의 개수에 변화가 생긴다. 사이클 위에 있는 정점은 모두 사이클을 도는 두 가지의 방향에 따라 단순 경로가 생기고, 그 외에도 사이클 위에 있는 정점에서 다른 사이클 위에 있는 정점과의 간선을 제거해 얻을 수 있는 각 트리 간의 단순 경로 역시 2개이다. 즉, 사이클 위에 있는 각 정점에서 다른 사이클 위에 있는 정점과의 간선을 제거해 얻을 수 있는 트리들을 구하고, 각 쿼리마다 들어오는 정점들이 서로 다른.. 2023. 2. 18. 이전 1 다음