알고리즘/백준
백준 23911 Beauty of tree
6epsilon
2023. 2. 16. 07:55
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에 대해서도 똑같이 하면 된다.