각 정점에 1에서 n까지 레이블이 지정된 n개의 정점이 있는 트리가 있다고 가정합니다. 트리의 루트는 레이블이 1이고 각 정점의 가중치는 wi입니다. 이제 A(x,y) =Wf(x, y)인 nxn 행렬 A가 형성됩니다. 여기서 f(x, y)는 정점 x와 y의 최소 공통 선행자입니다. 행렬 A의 행렬식을 찾아야 합니다. 행렬의 모서리, 가중치 및 총 정점 수가 입력으로 제공됩니다.
따라서 입력이 input_array =[[1, 2], [1, 3], [1, 4], [1, 5]]와 같으면 weights =[1, 2, 3, 4, 5], 꼭짓점 =5이면 출력은 24가 됩니다.
행렬 A는 =
| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 1 | 1 | 1 |
| 1 | 1 | 3 | 1 | 1 |
| 1 | 1 | 1 | 4 | 1 |
| 1 | 1 | 1 | 1 | 5 |
이 행렬의 행렬식은 24입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- w :=빈 목록
- 0에서 정점까지의 범위에 있는 i에 대해
- w에 가중치[i] 및 새 목록 추가
- 각 i에 대해 enumerate(input_array)의 항목, do
- p :=항목[0]
- q :=항목[1]
- w[p - 1, 1] 끝에 q - 1 삽입
- w[q - 1, 1] 끝에 p - 1 삽입
- det :=1
- stack :=튜플(0, 0)을 포함하는 스택
- 스택이 비어 있지 않은 동안 수행
- i, weights :=스택에서 최상위 요소 삭제
- det :=(det * (w[i, 0] - 가중치)) 모드 (10^9 + 7)
- w[i][1]의 t에 대해, do
- 스택에 (t,w[i,0])을 포함하는 튜플 추가
- w[i][1]의 각 t에 대해 다음을 수행합니다.
- w[t,1]에서 i 삭제
- 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(input_array, weights, vertices): w = [[weights[i],[]] for i in range(vertices)] for i, item in enumerate(input_array): p,q = item[0], item[1] w[p - 1][1].append(q - 1) w[q - 1][1].append(p - 1) det = 1 stack = [(0,0)] while stack: i, weights = stack.pop() det = (det * (w[i][0] - weights)) % (10**9 + 7) stack += [(t,w[i][0]) for t in w[i][1]] for t in w[i][1]: w[t][1].remove(i) return det print(solve([[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5))
입력
[[1, 2], [1, 3], [1, 4], [1, 5]], [1, 2, 3, 4, 5], 5
출력
24