스패닝 트리 경로를 따라 가장 길게 이동하다가(x가중치 적용)... 더이상 이동할 곳이 없으면 점프하여(y가중치 적용) 다시 트리 경로를 따라 이동하는 경로를 찾는 것이므로
본문에 글처럼 최장 경로를 하나만 찾는 문제가 아님.
풀이:
D[x][0] = x정점을 포함한 하위 트리의 모든 순회에 드는 점프 횟수
D[x][1] = 경로의 모양 (x에서 끝날시 D[x][0], 잎에서 끝날시 D[x][0]+1
임의의 경로 시작점 root가 있다고 할 때
1) 자식의 경로가 해당 자식에서 끝나는 자식이 2개 이상 있다면 Child D([0],[1]) = (a,a+a)
자
식에서 시작해서 루트를 거쳐 또 다른 자식으로 이동할 수 있으므로 Root D([0],[1])은 = (sum,sum+1) 형태가
되어야 한다. (b는 sum(왜냐하면 자식들의 점프횟수만큼만 모두합하면 되기 때문, b+1되는 이유는 root에 대한 경로가
root에서 끝나지 않고 자식에서 끝나므로(정확히는 잎) 모양을 결정.
2)자식의 경로가 해당 자식에서 끝나는 자식 C가 1개 있다면
Root D([0],[1]) = (sum,sum) 형태가 되어야 함. sum은 자식들의 sum 그리고 C에서 root로 올라오기만 하면 되므로 점프는 더 이상 필요없으니 sum 그대로에
C에서 root로 이동하면 root에서 끝나기 때문에 모양은 (a,a)가 된다.
3)자식의 경로가 해당 자식에서 끝나는 자식이 없다면
Root D([0],[1]) = (sum+1, sum+1) 왜냐하면, 자식들 모두 돌고나서 root로 점프해야하므로 sum+1이 되고, 마지막으로 root에서 끝나니 (a,a)형태가 되어야함.
드디어 해결!!
mathop 8년 전 1
코드포스 wunder 대회 끝난 후 풀이를 보며 공부하는 중에 도저히 해석이 안되는 코드가 있어서 질문 드립니다.
문제 : http://codeforces.com/contest/618/problem/D
풀이 : http://codeforces.com/submissions/SimpleToo
문제해석: 정점 개수 n인 undriected 스패닝 트리가 주어질 때,
각 정점을 한번씩만 거쳐 모두 방문하는 경로를 구성하려한다.
이 때 임의의 정점 u에서 v로 이동할 때 간선이 존재한다면 x시간이 걸리고 존재하지 않는다면 y시간이 걸린다.
입력: n,x,y
n-1라인에 간선 정보 (u,v)가 주어질 때 최소 시간을 구하시오.
i) x>=y
star(한 정점이 나머지 모든 정점에 연결된 스패닝 트리) 모양인 경우 간선을 한번은 써야하므로 x+(n-2)*y;
star모양이 아닌 경우 (n-1)*y
ii)x<y
스패닝 트리 간선을 최대한 이용하는 것이 유리하므로 주어진 스패닝 트리에서 최장 경로를 찾는다.
찾은 최장 경로 길이가 L이라면 답은 L*x+ (n-1-L)*y
제가 생각한 최장 경로를 구하는 법은 임의의 정점을 root로 하여 연결된 자식의 높이를 재귀 호출로 모두 구하여 가장 높은 두 높이에 대하여 잎->root->잎 경로가 최장 경로인지 확인한다. 재귀 호출 과정중에도 같은 계산을 하여 잎->자식->잎인 경우도 고려하여 longest를 갱신. 반환값은 높이.
이렇게 풀 경우 O(V^2)이 걸리는 것 같습니다.
그러나 정답 소스에서는 DP로 풀고 있는데 이 소스가 도저히 이해가 안되서 4시간 분석하다가 포기하고 절실한 도움을 요청합니다...
dp[i][j]가 무슨 의미인지 도저히 모르겠습니다.