개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다. 선발고사 문제 치고는 꽤 쉽다. 하지만 구현이 만만치 않다... 예제 속 그림을 보면 중요한 관찰이 눈에 쉽게 보인다. 바로 두 경로는 수직 구간 혹은 수평 구간을 정확히 하나 공유한다는 것이다. 이를 바탕으로 수평에 대해서 한 번 풀어주고, 수직에 대해서 같은 방식으로 한 번 풀어준다고 생각하고 한쪽만 고려해보자. 수직 구간을 공유한다면 수직 구간의 양 끝점을 기준으로 경로가 정확히 나뉜다. 이를 구간합 배열을 잘 이용하여 합쳐주면 된다. 솔직히 좋은 문제는 아니라고 생각한다... #include #define rep(i,a,b) for (auto i = (a); i = (a); --i) #define siz(x) int((x).si..

개인적으로 백준에서 보는 것보다 pdf로 보는 게 더 편한 것 같다. 한 자릿수 서브태스크 배점들을 보고 왜 이렇게 짜게 주나 했는데, 하나씩 풀다 보니까 기가 막힌 점수 배분인 것 같다. 부분 문제 1 ~ 4 풀이는 노드의 번호를 1-base 기준으로 작성했고, 부분 문제 5 풀이는 0-base 기준으로 작성했습니다. 궁금하신 점은 댓글로 남겨주시면 답변해 드리겠습니다! 문제 요약 "모든 $[i,j]$꼴의 정점 집합에 대해 만들어진 각 virtual tree의 가중치의 합을 구하라." 정도이다. 부분 문제 1 (5점) $N\le 300$이다. $O(N^3)$이 넉넉하게 돌아갈 수준이다. 모든 $[i,j]$를 직접 돌면서 dfs를 돌리면 된다. 웬만해서는 코드를 짜보려고 했는데, 점수 대비 구현량의 가성..