블로그 옮겼습니다

문제 링크 노드의 수가 100개 이하인 두개의 트리 g1, g2 가 주어진다. 두 트리의 루트 노드는 모두 1번 노드이다. 두 트리의 최대 공통 노드 수를 출력하는 문제이다. 쉽게 말해서 각 노드에 대해서 자식 노드들의 순서를 요리 조리 바꿔도 여전히 같은 트리이기 때문에 각 노드의 자식들의 순서를 요리 조리 바꿨을 때 두 트리중 모양이 일치하는 가장 노드가 많은 부분 트리의 노드 수를 구하는 문제이다. dp[a][b] : 트리 g1에서 노드 a를 루트로 하는 서브트리와, 트리 g2에서 노드 b를 루트로 하는 서브트리의 최대 공통 노드 수 라고 부분 문제를 정의하면 트리 dp 로 해결할 수가 있다. 그렇다면 부분 문제 테이블의 하나의 셀을 어떻게 채울까? 답은 MCMF 이다. dp[a][b] 에서 a의 ..

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3883 노드가 N개인 트리가 주어진다. 트리의 각 노드에 최대 한개의 식물을 놓아 간선들을 보호해야한다.식물은 세가지가 있다. 1번 : $100 이며 인접한 간선 하나 보호가능2번 : $175 이며 인접한 간선 두개 보호가능3번 : $500 이며 인접한 모든 간선 보호가능 간선을 모두 보호하기 위해 필요한 최소 비용을 구하는 문제이다. dp[i][j] : i는 현재 노드, j는 나의 부모를 연결하는 엣지를 부모가 보호해줬는지 여부 true/false 일 때인접한 간선을 모두 보호하기 위한 최소 비용 이라고 부분문제를 정의해 보자. 그럼 dp[i][0] 은 ..

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=4153 n개의 노드로 이루어진 트리가 있고 간선에는 기중치가 있다.q개의 쿼리가 주어진다.각 쿼리마다 연료의 양 x가 주어진다.루트노드부터 시작하여(루트 노드는 암시적으로 결정되어있음) 연료 x로 방문할 수 있는 최대 노드의 수를각 줄에 출력한다. 이 문제는 트리 dp 문제인데 부분문제를 두개 정의해야 한다. dp1[i][j]= 노드 i를 루트로 하는 서브트리에서부터 (현재노드포함) j개의 노드를 방문하고 돌아오는 최소비용 dp2[i][j]= 노드 i를 루트로 하는 서브트리에서부터 (현재노드포함) j개의 노드를 방문하고 안돌아와도 되는 최소비용 dp1은 d..

문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{K}\leq{200}\) 이 문제는 N개의 노드로 이루어진 트리가 주어진다. 각 노드에는 가중치가 있다.K가 주어지는데 최대 K번 가지를 칠 수 있다는 것이다. 어떤 노드 u를 가지친다는 말의 정의는노드 u를 루트로 하는 서브트리를 제거한다는 것이다. 최대 K번 가지를 쳐서 남아있는 트리의 모든 노드의가중치의 합을 최대로 하고싶을때 이 최대 가중치합을 구하는 문제이다. 우선 처음에 일반적인 트리dp 문제처럼 이렇게 풀어 보려고했었다.dp[u][v][k] : 현재 노드 u를 보고있고 v개의 자식을 이미 봐주었으며 앞으로 최대 k번 가지칠수있을 때 최대 가중치 합 이렇게 하면 부분문제의 수는 최대 N*K 개이다. 왜냐하면 (u,v) 의 쌍은 간..

사실 원래의 풀이와 아주 큰 차이는 없다. 두번의 dfs를 돌리는 것까지는 똑같지만 변수가 하나 줄었고, 점화식이 좀 더 단순해 졌다. 우선 size(i) 는 i를 루트로 갖는 서브트리의 총 노드수라고 보면노드 i 부터 자손들까지의 거리의 총합 S(i)는,노드 i의 자식이 c1, c2, c3..... cn 이고, ck 와 연결된 간선의 가중치는 wk 일때size(c1)*w1 + size(c2)*w2 +....+size(cn)*wn +S(c1) + S(c2) + S(c3) +.....+S(cn) 이다.즉 각각의 간선에 대해 몇번 지남당하는지를 계산한다고 보면된다. 이렇게 각각의 간선에 대해 몇 개의 경로에 대해 지남 당하느냐로거리 의 총합을 구하는 경우가 많은 것같다. 트리상에 존재하는 모든 정점쌍간의 거..

우선 이 문제를 풀기 위해서 한가지 선행 지식이 필요하다. N개의 노드를 가진 트리에서 모든 정점 쌍의 거리의 합을 O(N)에 구할 수가 있는데 size(i) = i번 노드를 루트로 갖는 서브트리의 노드의 수. 로 정의하여 재귀적으로 모든 노드에 대해 구하면서 각 간선을 지나는 경로의 수를 dfs로 구하는것이다. 이 전, 전 포스트에 설명이 되어있다. 하지만 이 문제는 점프 거리 k 라는 입력이 주어져서 한번에 k개의 간선을 뛰어넘을 수가 있고, 단순히 모든 정점쌍 사이의 거리의 합이 아니라 모든 정점 쌍 사이의 경로를 가기위한 점프 횟수의 합을 요구한다. 그렇기 때문에 최대 점프거리 k가 3일때, 거리가 3인 경로는 3이 아니라 1이 더해져야하고 4인 경로는 4가 아니라 2가 더해져야하는 식이다. 여기..

이 문제는 N개의 노드를 가지고 간선에 가중치가 있는 트리에서 중앙 정점이라는 것을 찾아서 이 중앙 정점에서 다른 정점까지의 모든 거리의 합을 구하는 문제이다.중앙 정점의 정의는 어떤 한 점에서 다른 모든 정점까지의 거리의 합이 최소가 되는 점이다. 처음에 트리의 중심과 헷갈려서 트리의 중심으로 풀 뻔 했는데 잘 생각해 보면 트리의 중심은 어떤 한 점에서 다른 모든 정점까지의 거리의 최대값이 최소가 되는 점이기 때문에 확실히 다른 개념이다. 그렇다면 이 중앙 정점이라는 것은 어떻게 구할까? naive 하게는 각 N개의 정점에서부터 BFS나 DFS를돌려서 한 점에서 다른 모든 점까지의 거리의 합을 구하고 이 값을 바탕으로 최소값을 갱신해 나가는 O(N^2) 의 방법이 있을 것이다. 하지만 N이 10000 ..