동적 숲의 경로 합
다이아몬드 V의견: 0
\(N\)개의 정점으로 이루어진 숲(forest)이 있다. 처음에는 간선이 하나도 없으며, 각 정점 \(i\)에는 정수 가중치 \(w_i\)가 부여되어 있다.
다음 네 종류의 연산 \(Q\)개를 순서대로 처리해야 한다.
-
1 u v: 정점 \(u\)와 \(v\) 사이에 간선을 추가한다. (추가 전 두 정점은 서로 다른 트리에 속함이 보장된다.) -
2 u v: 정점 \(u\)와 \(v\) 사이의 간선을 제거한다. (현재 그 간선이 존재함이 보장된다.) -
3 u x: 정점 \(u\)의 가중치를 \(x\)로 바꾼다. -
4 u v: \(u\)에서 \(v\)로 가는 경로 위 정점들의 가중치 합을 출력한다. 두 정점이 서로 다른 트리에 속해 경로가 없으면 \(-1\)을 출력한다.
트리 구조가 동적으로 바뀌므로 정적 자료구조로는 처리할 수 없다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 200{,}000\)
\(-10^9 \le w_i, x \le 10^9\)
\(1 \le u, v \le N\)
첫째 줄에 정점 수 \(N\)과 연산 수 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 가중치 \(w_1, \dots, w_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 위 형식의 연산이 주어진다.
각 4 연산에 대해 경로 가중치 합(경로가 없으면 \(-1\))을 한 줄에 하나씩 출력한다.
4 8
1 2 3 4
1 1 2
1 2 3
4 1 3
3 2 10
4 1 3
2 2 3
4 1 3
4 1 2
6
14
-1
11가중치 \([1,2,3,4]\). 1-2, 2-3을 이으면 경로 1→3 합은 \(1+2+3=6\). 정점 2를 10으로 바꾸면 \(1+10+3=14\). 2-3 간선을 끊으면 1과 3은 분리되어 \(-1\), 1→2 경로는 \(1+10=11\).
2 4
5 7
4 1 2
1 1 2
4 1 2
4 1 1
-1
12
5처음엔 간선이 없어 1→2는 \(-1\). 간선을 이으면 \(5+7=12\). 1→1은 자기 자신뿐이라 \(5\).
riseoj 작성
출처 Original
평가 및 의견
동적 숲의 경로 합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
동적 숲의 경로 합