Star Tree

서브태스크 1: 직접 갱신

쿼리마다 BFS로 $x$에서 $y$까지의 경로를 찾고, 경로를 $x$부터 읽으며 $1,2,\ldots$를 직접 더한다. 시간은 $O(N+NQ)$, 공간은 $O(N)$이다. $N,Q\leq2000$이면 충분하다.

서브태스크 2: 번호순 경로

간선이 $\{i,i+1\}$ 형태이면 경로가 정수 구간이다. $x<y$인 쿼리는 구간 $[x,y]$의 정점 $v$에 을 더하고, 이면 구간 에 을 더한다. 두 차분 배열에 의 계수와 상수항을 각각 더한 뒤 누적합을 구하면 시간, 공간에 처리한다.

전체 풀이: 깊이의 일차식

정점 $1$을 루트로 잡고, 깊이를 $d(v)$, 부모를 $p(v)$라 하자. 루트의 깊이는 $0$, 부모는 가상 정점 $0$이다. 쿼리 $(x,y)$의 두 정점의 LCA를 라 하자. 경로를 부터 까지의 구간과 다음 정점부터 까지의 구간으로 나눈다.

첫 구간의 정점 $v$에 더할 값은

$$d(x)-d(v)+1=-d(v)+(d(x)+1)$$

이다. 두 번째 구간에서는

$$d(x)-d(z)+d(v)-d(z)+1=d(v)+(d(x)-2d(z)+1)$$

이다. 따라서 경로의 각 절반에 깊이의 계수와 상수항을 따로 더하면 된다. $z$는 첫 구간에만 포함시켜 중복 계산을 막는다.

조상 경로에 상수를 더하는 트리 차분

$w$가 $u$의 조상일 때, $u$부터 $w$까지 모든 정점에 상수 $c$를 더하려면 차분 배열 $D$에

$$D[u]\mathrel{+}=c,\qquad D[p(w)]\mathrel{-}=c$$

를 기록한다. 모든 기록 후 자식의 값을 부모에게 더하며 아래에서 위로 누적한다. 어떤 정점의 최종 값은 자신의 서브트리에 들어 있는 차분의 합이다. $u$에서 시작한 기여는 $w$까지 도달하고, 그 위에서는 $p(w)$의 반대 기록과 상쇄된다.

깊이의 계수용 배열 $A$와 상수항용 배열 $B$를 둔다. 한 쿼리마다 $c_1=d(x)+1$, ${}_{}$로 놓고 다음을 수행한다.

$$A[x]\mathrel{-}=1,\quad B[x]\mathrel{+}=c_1,$$ $$A[p(z)]\mathrel{+}=1,\quad B[p(z)]\mathrel{-}=c_1,$$ $$A[y]\mathrel{+}=1,\quad B[y]\mathrel{+}=c_2,$$ $$A[z]\mathrel{-}=1,\quad B[z]\mathrel{-}=c_2.$$

두 번째 경로는 $z$를 제외하므로 $p(z)$가 아니라 $z$에서 취소한다. $y=z$라면 이 두 기록은 즉시 상쇄되어 빈 구간을 올바르게 처리한다.

모든 쿼리를 기록한 뒤, 부모가 자식보다 먼저 나오는 순서의 역순으로 각 정점 $v$의 $A[v],B[v]$를 부모에게 더한다. 가상 정점 $0$의 값은 출력하거나 실제 정점에 다시 더하지 않는다. 답은

$$A[v]d(v)+B[v]\pmod{998\,244\,353}$$

이다.

정당성과 복잡도

두 경로 구간은 원래 경로를 중복 없이 나누고, 위의 두 일차식은 각각 $x$로부터의 거리에 $1$을 더한 값이다. 트리 차분은 각 구간의 모든 정점에만 원하는 계수를 더한다. 선형성에 의해 모든 쿼리를 모아서 한 번에 누적해도 각 쿼리를 직접 처리한 결과와 같다.

이진 리프팅으로 LCA를 구하면 전처리 $O(N\log N)$, 쿼리당 $O(\log N)$, 마지막 누적 $O(N)$으로 총 $O((N+Q)\log$ 시간, 공간이다. 인 경우에는 가능한 쿼리가 없으며 답은 이다. 깊이 인 트리도 들어오므로 부모·깊이 계산과 마지막 누적은 재귀 없이 구현한다.

독립 검증 풀이

별도의 HLD 풀이는 경로를 진행 방향이 있는 연속 번호 구간들로 나눈다. $x$쪽에서 얻은 구간은 그대로, $y$쪽에서 얻은 구간은 역순으로 이어 붙인다. 다음에 더할 수를 유지하면 각 구간에 대해 번호의 계수 $+1$ 또는 $-1$과 상수항을 구할 수 있다. 이 값을 일반 배열의 구간 차분으로 처리한다. LCA의 깊이로 위 일차식을 만드는 대신 실제 구간의 순서와 길이를 사용한다. 시간은 $O(N+Q\log N)$, 공간은 이다.

정수 범위

한 정점의 최종 정수 값은 $QN\leq2.5\cdot10^{11}$이다. 차분의 상수항과 음수 중간값까지 포함해 정해의 연산은 signed 64-bit 범위에 충분히 들어간다. 차분을 32비트 정수로 저장하거나 두 32비트 값을 먼저 곱한 뒤 64비트에 담으면 안 된다. 모든 누적을 64비트로 처리한 뒤 출력할 때 나머지를 구해도 된다.

Solution written by GPT6