https://www.acmicpc.net/problem/23911
23911번: Beauty of tree
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the three integers N, A and B. The second line contains N-1 integers. The i-th integer is the parent of node i+1.
www.acmicpc.net
각 지점에서 (A에 의해 방문될 확률)+(B에 의해 방문될 확률)-(두 확률의 곱)의 총합을 구하면 됨을 알 수 있다. (두 사건은 독립이기 때문이다.)
A에 의해 방문될 확률은 A가 이 정점을 방문하는 정점을 고르는 확률이므로, 방문 과정에서 이 정점을 방문하게 되는 정점의 개수를 따져 주면 된다. 이는 자기 자신과 자신의 서브트리 중에서 깊이가 a, 2a, .. 차이나는 정점들이다. 차이가 2a나는 것 부터는 차이가 a나는 것에서 카운트한걸 활용할 수 있으므로 DP를 할 수 있다.
이제 이 DP를 업데이트하는 것은 DFS를 돌면서, 조상 정점들을 저장하는 스택을 관리할 것이다. 자신의 서브트리에 대한 업데이트가 끝나면 a번째 조상에 지금 정점의 값을 업데이트해주면 된다. B에 대해서도 똑같이 하면 된다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 19848 빈 문자열 만들기 (0) | 2023.02.25 |
|---|---|
| 백준 8225 Tour de Byteotia (0) | 2023.02.16 |
| 백준 4792 레드 블루 스패닝 트리 (0) | 2023.02.15 |
| 백준 15480 LCA와 쿼리 (0) | 2023.02.14 |
| 백준 1772 정원 정리 (0) | 2023.02.09 |
