BOJ 10089 profit

www.acmicpc.net/problem/10089

10089번: Profit

문제 내용을 간단하게 요약하면 트리가 있고 우리는 그 위에 하나의 경로를 잡을 것이다. 그런데 트리에는 M개의 경로가 있는데, 각각의 경로를 포함하게 되면 그 경로에 해당하는 주어진 수익을 얻을 수 있다. 이때 얻는 수익을 최대화하면 된다.

정한 경로의 양끝점을 p1,p2라고 하자. p1에서 p2로 이어지는 경로가 어떤 경로를 포함하려면, p1이 그 경로의 한쪽 끝점에서 만들어지는 서브트리에 포함되고, p2가 그 경로의 또다른쪽 끝점에서 만들어지는 서브트리에 포함된다. 그런데 루트를 잡고 dfs ordering을 한다면 모든 서브트리는 한 개 또는 두 개의 구간(루트를 포함하는 서브트리일 때)으로 나타낼 수 있다. p2의 dfs order가 p1의 dfs order보다 크다고 일단 고정하자. 그러면 모든 경로들은 한 개 또는 두 개의 'p1의 dfs order가 l1~r1 사이에 있고 p2의 dfs order가 l2~r2 사이에 있을 때 wi의 이득을 얻는다.'라는 표현으로 나타낼 수 있다. 이렇게 나타내면 p1의 dfs order가 커지는 순서로 스위핑하면서 레이지 최댓값 세그를 이용하면 문제를 풀 수 있다.