給定一棵樹，在樹上每個點處有$1$個人，每個人有一個忍耐程度$t_i$。當一個人子樹內放假的人數$\gt t_i$且他沒有放假的時候，他會刪庫跑路。初始時所有人都沒放假。有$m$次操作，每次將一個人由放假變為不放假或由不放假變為放假，然后輸出一共有多少個人會刪庫跑路。 $n,m\leq10^5,\ 0\leq t_i\leq n$。

題目鏈接

是19年四五月看的題，但咕咕了

---

\(Description\)
給定一棵樹，在樹上每個點處有\(1\)個人，每個人有一個忍耐程度\(t_i\)。當一個人子樹內放假的人數\(\gt t_i\)且他沒有放假的時候，他會刪庫跑路。初始時所有人都沒放假。有\(m\)次操作，每次將一個人由放假變為不放假或由不放假變為放假，然后輸出一共有多少個人會刪庫跑路。
\(n,m\leq10^5,\ 0\leq t_i\leq n\)。

\(Solution\)
\(Sol1\)
令\(A_i=t_i-x\)，\(x\)是\(i\)子樹內有多少人放假了。就是維護\(A_i\lt0\)且沒有放假的人的個數。
樹剖+分塊。對DFS序分塊。記\(s[i][j]\)為第\(i\)塊內\(A_x=j\)且沒放假的人的個數。每次修改只會影響一個位置的值，很容易維護。
一個空間上的優化是，記\(tag[i]\)為第\(i\)塊的整體加標記。我們限制\(s\)的第二維在\([-D,D]\)范圍內（只在這個范圍內統計），這樣空間就是\(O(塊數*D)\)的。因為\(|tag[i]|\lt D\)時顯然不會有\(x\)影響答案。而當\(tag\geq D\)時，暴力重構這個塊即可。

\(Sol2\)
虛樹+分塊。對詢問分塊，每次處理\(O(B)\)個詢問。容易發現樹被分成了\(O(B)\)條鏈，同一條鏈上的點，被修改的值是相同的。
我們可以\(O(B)\)建出虛樹。考慮如何回答每次詢問。設\(A_i=t_i-x\)，把每一條鏈上的點先按\(A_i\)排序，然后維護一個指針，表示當前第一個\(\lt0\)的位置在哪。將重復的\(A_i\)合并到一起，每次更新一條鏈最多只會移動一下指針，是\(O(1)\)的。排序可以用基數排序。
處理完\(B\)個詢問后更新一下所有\(A_i\)即可。
復雜度\(O(\frac{n^2}{B}+nB)\)，也就是\(O(n\sqrt n)\)。

---

代碼咕了（兩年半了），見 http://codeforces.com/contest/966/status/E?order=BY_CONSUMED_TIME_ASC