06vfsunny   1년 전

아래와 같이 코드를 짰는데 기본적인 아이디어는

1. 1번 노드를 언제나 루트로 잡음.

2. size[n]배열에 각 노드마다 자식 노드+자기 자신의 총 개수를 넣음

3. 이후 sumdp[n] 배열에 각 자식 노드들이 자신의 부모 노드에 도달하기까지 최단거리 합을 저장해놓음

ex) 만약 입력이

3

1 2 3

2 3 7

이렇게 주어지면 1번 노드를 루트로 해서 size[0]에는 자식노드 개수 2+자기 자신으로 해서 size[0]=3, size[1]=2, size[2]=1;

이후 sumdp에는 3번 노드는 자식이 없으니 sumdp[2]=0, sumdp[1]=7, sumdp[0]=13이런 식으로 올라감

4. 위의 과정이 끝나면 사전 준비는 완료된 것이고 이제 진짜 dp 실행

5. for문으로 루트를 제외한 각 노드들을 방문하며 각 노드를 방문할 때마다 while문과 stack으로 자신의 부모를 타며 올라감

만약 끝까지 올라가서 루트까지 닿는다면 루트 직전 노드를 a라고 하자. 그럼

a의 전체 최단거리 합=sumdp[루트]+a와 루트 사이 거리*(루트를 포함한 a외부 트리에서 개수(a의 자식이 아니고 a 자신도 아닌 노드들 개수)-a 자신 사이즈)

이렇게 성립이 되고 

dp[a]=a의 전체 최단거리 합-sumdp[a]

이렇게 dp를 저장하고 이후 다시 루트에서 stack을 pop하며 내려가면

특정 노드 n의 최단거리 합은 dp[n부모]+sumdp[n부모]+(부모와의 간선 거리)*(n의 외부트리 노드 개수-((n 자식 노드 개수)+1)(이것도 결국에는 n 자신 사이즈))

dp[n]은 n최단거리 합-sumdp[n]

이런 식으로 점화식을 만들어서 했는데 왜 안될까요.... 아니 50% 정도까지는 잘 갔는데 갑자기 틀렸습니다가 나와서 진짜 너무 슬픕니다. 제발 도와주세요

06vfsunny   1년 전

풀었습니다.... 그냥 int형을 long으로 고치니까 되네요...

여러분은 이런 실수하지 마세요ㅠ

nabina1395   1년 전

거리의 합이 대략 d * N^2에 비례해서 int는 오버플로우가 나요

nabina1395   1년 전

ㄲㅂ

댓글을 작성하려면 로그인해야 합니다.