쿼리 종류가 다양해서 복잡해 보이지만, 결국은 기본적인 연산들이고, 풀이 자체는 새로운 아이디어를 필요로 하는 것은 없다.
트리에서의 경로 쿼리와, 서브트리 쿼리를 구간 쿼리로 변환하는 것은 Heavy Light Decomposition의 기본적인 연산들이다
구간에 대해서 구간 합 업데이트/구간 곱 업데이트/구간 합 쿼리를 처리하는 것은, 두 종류의 업데이트를 x := ax+b 의 선형 변환 업데이트로 합쳐서 처리할 수 있다. 이것을 레이지 세그먼트 트리로 처리하는 것은 정확히 수열과 쿼리 13 와 동일하다. 풀이는 이쪽을 참조.
HLD와 세그먼트 트리 구축은 O(n)에 가능하고, 경로에 대한 업데이트와 쿼리는 O(log^2n)에, 서브트리에 대한 쿼리와 업데이트는 O(logn)에 처리 가능하다. 총 시간 복잡도는 O(n+qlog^2n)
n⇐500,000, q⇐100,000 인데 시간 맞추기가 꽤 타이트하다. Python으로는 TLE가 나고, PyPy로 제출해야 약 8000ms 로 겨우 통과된다,