• HLD + lazy segment tree
• 쿼리 종류가 다양해서 복잡해 보이지만, 결국은 기본적인 연산들이고, 풀이 자체는 새로운 아이디어를 필요로 하는 것은 없다.
• 트리에서의 경로 쿼리와, 서브트리 쿼리를 구간 쿼리로 변환하는 것은 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 로 겨우 통과된다,

(다이아몬드 이상은 코드 생략)

• Dependency
  • teflib.segmenttree.LazySegmentTree
  • teflib.ttree.HeavyLightDecomposition