마법 토끼

먼저 기존 그래프의 Kruskal reconstruction tree를 만든다. 어떤 두 정점 사이의 최대 병목값은 Kruskal tree에서 두 정점의 LCA 값으로 표현된다.

정점 $t$에서 끝나는 여행을 고정하자. 정점 $v$의 마나 하나를 $k$번째로 줍는다면, 그 직후 마나 $k$개를 들고 $v$에서 $t$까지 갈 수 있어야 한다. 따라서 각 마나 하나는 deadline을 가지는 작업으로 볼 수 있다.

deadline이 $d$인 마나가 $c$개 있을 때의 greedy 전이는

$$x \mapsto \min(d,x+c)$$

이다. 동치로, 답은

$$\min_D \left(D+\text{deadline이 }D\text{보다 큰 마나 수}\right)$$

로 볼 수 있다.

쿼리 간선 $(s,t,w)$를 추가하면, threshold가 $w$보다 작은 구간에서 $s$쪽 컴포넌트와 $t$쪽 컴포넌트가 임시 간선으로 연결된다. 따라서 Kruskal tree 위에서 두 컴포넌트를 가중치 내림차순으로 끌어올리며 후보값을 갱신한다.

직접 쿼리마다 경로를 끝까지 올라가면 $O(QH)$ 풀이가 된다. 특수조건 B에서는 기존 그래프가 경로이고 가중치가 무작위이므로 Kruskal tree가 랜덤 Cartesian tree가 되어 높이가 기대 $O(\log N)$이다.

전체 풀이에서는 Kruskal tree 위에 특별 정점을 잡는다. 임의의 정점에서 가장 가까운 특별 조상까지의 거리가 $O(\sqrt N)$이 되게 하면, 쿼리 하나는 직접 $O(\sqrt N)$번만 올라가다가 특별 정점에 도달한다.

특별 정점 $b$가 한쪽 끝인 모든 남은 쿼리는 한 번에 처리한다. $b$에서 root까지의 chain에 있는 type X 연산의 prefix를 전처리하고, 반대쪽 endpoint들의 type Y 연산을 DFS 순서로 동시에 시뮬레이션하면 특별 정점 하나당 $O(N)$에 모든 값을 얻을 수 있다. 특별 정점 수가 $O(\sqrt N)$개이므로 전체 시간 복잡도는 $O(N\sqrt N)$이다.