경로 최솟값 갱신과 합
다이아몬드 III의견: 0
\(N\)개의 정점으로 이루어진 트리가 있다. 정점 \(i\)에는 정수 \(a_i\)가 적혀 있다. 다음 세 종류의 연산을 \(M\)번 처리해야 한다. 모든 연산은 정점 \(u\)와 \(v\)를 잇는 트리 경로 위의 정점들에 대해 정의된다.
-
1 u v x: 경로 위 모든 정점 \(i\)에 대해 \(a_i \leftarrow \min(a_i, x)\) 로 갱신한다. -
2 u v: 경로 위 모든 정점의 값의 합을 출력한다. -
3 u v: 경로 위 모든 정점의 값의 최댓값을 출력한다.
\(1 \le N \le 100{,}000\)
\(1 \le M \le 100{,}000\)
\(0 \le a_i, x \le 10^9\)
\(1 \le u, v \le N\)
첫 줄에 정점 수 \(N\)과 연산 수 \(M\)이 주어진다.
둘째 줄에 \(a_1, a_2, \dots, a_N\)이 주어진다.
다음 \(N-1\)개의 줄에 트리의 간선 \(a\), \(b\)가 주어진다.
이어서 \(M\)개의 줄에 위 형식의 연산이 주어진다.
2, 3 연산마다 답을 한 줄에 하나씩 출력한다.
4 4
5 3 8 1
1 2
1 3
3 4
2 2 4
1 1 4 4
3 2 4
2 1 3
17
4
8경로 2-1-3-4 값 합 처음 5+3+8+1... 첫 질의 경로 2..4는 {2,1,3,4}=3+5+8+1=17. 그 다음 min(.,4) 적용 후 {2,1,3,4}={3,4,4,1}. 경로 2..4 최댓값=4. 경로 1..3 합=4+4=8.
5 4
10 9 8 7 6
2 1
3 2
4 3
5 4
2 1 5
1 2 4 7
3 1 5
2 1 5
40
10
37사슬 1-2-3-4-5 값 10,9,8,7,6. 경로 1..5 합 40. min(.,7)을 경로 2..4에 적용하면 9,8→7,7 이 되어 값 10,7,7,7,6. 경로 1..5 최댓값 10, 합 37.
riseoj 작성
출처 Original
평가 및 의견
경로 최솟값 갱신과 합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
경로 최솟값 갱신과 합