Description

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

Input

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

Output

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

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

Source

葉聞捷出題 NOIP 模擬測試T4

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