34475번 - 배달 서브태스크

$N$개의 정점으로 구성되어 있고, 1번 정점이 루트인 트리가 주어진다. $i$번 정점에는 가치가 $A_i$인 물건이 $B_i$개 놓여있다. ($1 \le i \le N$; $1 \le B_i \le 3$)

1번 정점에 $N$명의 사람이 살고 있다. $i$($1 \le i \le N$)번째 사람은 1번 정점에서 출발해 $i$번 정점으로 최소한의 간선을 통과해서 이동하려고 한다. 이때, 이동하면서 통과하는 정점들에 놓인 물건들 중 원하는 것을 정확히 하나 선택해서 $i$번 정점으로 가지고 가야 한다.

아래 두 가지 종류의 쿼리가 총 $Q$번 주어진다. 쿼리는 누적되며, 여러분은 쿼리가 주어질 때마다 $N$명의 사람이 가지고 간 물건의 가치의 합으로 가능한 최댓값을 구해야 한다.

• $1$ $k$ $a$: 정점 $k$에 있는 물건의 가치를 $a$로 변경한다.
• $2$ $k$ $b$: 정점 $k$에 있는 물건의 개수를 $b$로 변경한다.

첫째 줄에 정점의 개수 $N$과 정수 $F$가 공백으로 구분되어 주어진다.

다음 $N$개의 줄에 걸쳐 각 정점에 놓인 물건의 정보가 주어진다. 그중 $i$ ($1 \le i \le N$)번째 줄에는 $A_i$, $B_i$가 공백으로 구분되어 주어진다.

다음 $N-1$개의 줄에는 간선의 정보가 주어진다. 각 줄마다 두 정수 $u$, $v$가 공백으로 구분되어 주어지며, 이는 정점 $u$와 정점 $v$가 간선으로 연결되어 있음을 의미한다.

그다음 줄에 쿼리의 개수 $Q$가 주어진다.

이후 $Q$개의 줄에 걸쳐 쿼리가 입력으로 주어지며, 쿼리는 세 정수 $w$, $x$, $y$로 이루어져 있다. $o = 1$일 때는 정점 $k$에 있는 물건의 가치를 $a$로 바꾸는 쿼리, $o = 2$일 때는 정점 $k$에 있는 물건의 개수를 $b$로 바꾸는 쿼리를 의미한다.

바로 직전 쿼리의 정답을 $p$라고 하면, 쿼리에서 사용되는 수 $o$, $k$, $a$, $b$는 아래 수식을 이용해 계산한다. $p$의 초깃값은 0이다.

• $o = (p \times F + w - 1 + 2) \mod 2 + 1$
• $k = (p \times F + x - 1 + N) \mod N + 1$
• $a = (p \times F + y - 1 + 10^9) \mod 10^9 + 1$
• $b = (p \times F + y - 1 + 3) \mod 3 + 1$

$Q$개의 줄에 걸쳐 답을 출력한다. $i$ ($1 \le i \le Q$)번째 줄에는 $i$번째 쿼리까지 차례대로 반영된 상황에서, $N$명의 사람이 갖고 간 물건의 가치의 합으로 가능한 최댓값을 출력한다.

• $2 \le N \le 100\,000$
• $0 \le F \le 1$
• $1 \le A_i \le 10^9$ ($1 \le i \le N$)
• $1 \le B_i \le 3$ ($1 \le i \le N$)
• $1 \le u,v \le N$
• $1 \le Q \le 100\,000$
• $0 \le w,x,y \le 10^9$
• 입력으로 주어진 그래프는 트리다.
• 입력으로 주어진 모든 수는 정수다.