====== 국제 메시 기구 ======

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


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

  * Dependency
    * [[ps:teflib:segmenttree#LazySegmentTree|teflib.segmenttree.LazySegmentTree]]
    * [[ps:teflib:ttree#HeavyLightDecomposition|teflib.ttree.HeavyLightDecomposition]]

{{tag>BOJ ps:problems:boj:다이아몬드_4}}