Description

費了一番功夫，神犇 CJK 終于完成了前三道題目。“不錯，不愧是新一代神犇 啊！” JesseLiu 滿意地說道，“不過，你在算法方面的功底固然不錯。對于數據結 構的運用，你又掌握地如何呢？” 聽到“數據結構”這四個字，就連身為神犇的 CJK 也不禁嚇出一身冷汗?！澳贻p 人，現在，對于我給定一棵樹，你需要完成以下操作： 1.修改某個點的權值； 2.查詢某兩點間路徑上所有點的權值和； 3.查詢某點子樹的權值和?！? CJK 臉上閃過一絲不屑：不就是道鏈剖裸題嗎？ “這只是第一問?！盝esseLiu 似乎也覺得這道題太水了，于是補充道：“完成以 上所有操作后，我還會有以下幾種詢問： 1. 詢問某個點子樹上有多少個點的權值小于等于 k； 2. 詢問某兩點之間的路徑上有多少點的權值小于等于 k；” 盡管 CJK 是神犇，但遇到這種題，也不禁感到一絲恐懼。還好，通過自己的 玄學力量，他聯系到了他的同學——你。現在，就請你 A 掉這最后一道水題。

Input

第一行一個數 n，表示點的總數。接下來 n-1 行，一行兩個整數 x 和 y，表示 x 和 y 之間有邊相連。接下來一個整數 m1，表示第一問中操作的數量。接下來 m1 行表示操作，格式如下： “1 x y”將點 x 的權值修改為 y； “2 x y”詢問 x 到 y 路徑上的點權之和（包括 x 和 y）； “3 x”詢問 x 的子樹上的點權和（包括 x）； 接下來一行 m2，表示第二問中操作的數量。接下來 m2 行描述操作，格式 如下： “1 x y z”詢問 x 到 y 的路徑上有多少個點的權值小于等于 z； “2 x y”詢問 x 的子樹上有多少個點的權值小于等于 y； 每個點的初始權值為 0,默認樹根為 1 號節點。

Output

對于每一次詢問，輸出一個整數表示詢問的答案。

Sample Input

樣例①：

3 1 2 1 3 3 1 1 3 1 3 1 3 1 2 2 1 2 1 1 3 1

樣例②：

5 1 2 1 3 3 4 3 5 5 3 1 1 3 1 2 4 5 1 4 -1 3 3 2 1 1 5 0 2 3 -1

Sample Output

樣例①：

4 2 1

樣例②：

0 1 0 2 1

Hint

對于 30%的數據，n<=100,m1<=100,m2<=100。剩下的數據保證 n<=50000； 對于另外 30%的數據，m2=0。其中有 1 組數據，樹退化為鏈; 對于 100%的數據， 保證 n<=50000,m1<=50000,m2<=50000， 保證題目中所有輸入、 輸出、中間運算不超過 int 范圍。

Source

葉聞捷出題 NOIP 模擬測試T4

這道題的第一問是一個樹鏈剖分，在此就不作贅述了。 對于第二問，我們可以采取一種離線算法： 先將線段樹中的值清空，然后將詢問與添加操作放入一個數組，按詢問（添加）的值從小到大排序，然后按順序一個一個詢問（添加），這樣可以保證在詢問時，線段樹中的值都小于等于k。