�ݺ�ߣ

<쟤가 몸통입니다(ID:BODY)> 풀이
https://algospot.com/judge/problem/read/BODY

예제 1번 데이터 :
2
1
5 6
3
4
2가 우두머리 일 때,
몸통 멤버의 가짓수?

2
1
5 6
3
4
2가 우두머리 일 때,
몸통 멤버의 가짓수?
= 2를 root로 하는,
size가 3인,
subtree의 개수

2
1
5
2
1
6
2
1 3
2
3
4
= 4가지 경우 존재

2
1
5 6
3
4
DP 구상
2
1
5 6
3
4
Size=3
=
Size=2

2
1
5 6
3
4
DP 구상
2
1
5 6
Size=2
3
4
=
Size=2
2
1
5 6
3
4
or
Size=1

2
1
5 6
3
4
DP 구상
2
1
5 6
Size=2
3
4
=
Size=2
2
1
5 6
3
4
or
Size=1
1
3
3+1=4

2
1
5 6
3
4
DP 구상
dp(i,j) =
[i..N]범위의 트리에서
j개를 선택하는 경우의 수

2
1
5 6
3
4
DP 구상
dp(i,j) =
[i..N]범위의 트리에서
j개를 선택하는 경우의 수
[i..N]범위의 트리?
= 전위순회한 결과를
이용한다!
(자주 쓰이는 방법)

2
1
5 6
3
4
DP 구상
2 1 5 6 3 4
전위순회
S[i] 6 3 1 1 2 1
(S[i]=sub-tree의 size)
dp[i][j]=dp[i+1][j-1]+dp[i+S[i]][j]
(i번째 element를 선택한 경우) (선택하지 않은 경우)

점화식 정리
dp[i][j]=[i..N]범위의 트리 내에서
j개를 선택하는 경우의 수라 정의할 때,
dp[i][0]=1 (모든 i에 대해)
dp[i][j]=dp[i+1][j-1]+dp[i+S[i]][j]
(j≠0일 때)

의사코드
1. A부터 B까지 경로를 찾아 root를 구함
2. 각 root에 대해서 dfs를 수행 : S[i] 세팅
3. dp[i][j]를 구함(i는 거꾸로 구해줘야)
4. dp[0][Q]가 정답이 됨

시간복잡도
• dp배열 순회에 지배
• 최대 N개의 root에 대해
N*Q의 반복문을 수행하므로,
• O(N²Q)=약 10^8번 연산!

제1회 알고스팟 새싹 콘테스트 G. BODY 풀이