[NPSC 2015]上司的薪水

NPSC官方網站好像找不到題目，所以做了題目備份，請參考～

這裡、這裡和這裡提供了另外幾項作法，選個喜歡的去實現吧～

可以觀察到，薪水$\geq K$的人的分佈會從根慢慢往下「擴散」並「分岔」

把這個過程倒回來，就變成了薪水$<K$的人慢慢往上「蔓延」並在交叉點「合併」，不會往回跑

假如我們能快速找出每次修改會影響到蔓延體的哪個頂端，並快速算出這個蔓延體頂端的薪水，就能判斷要不要繼續往上蔓延了

可以的！
可以利用並查集維護每個點沿著蔓延體往上會走到哪裡
利用懶惰標記可以在蔓延上去時把懶惰標記往上丟，並直接算出該節點的值

每蔓延一格，就把答案減一
請記得答案是倒著算出來的

時間複雜度：$O(Q\alpha(N))$ (實際上，我的並查集沒有特別優化到$O(\alpha(N))$，複雜度為$O(\log N)$)

code:

#include<cstdio>
#include<cassert>
#include<utility>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
int N,Q,PARENT[300000];
vector<int>ET[300000],TOPU;
LL K,COST[300001],TAG[300001];
int ANS[300000];
pair<int,LL>QUERY[300000];
int DJ[300001];
int Find(const int a){return DJ[a]==a?a:(DJ[a]=Find(DJ[a]));}
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
//    freopen("s1.in","r",stdin);
    while(scanf("%d%d%lld",&N,&Q,&K)==3)
    {
        for(int i=0;i<N;i++)ET[i].clear();
        for(int i=1,v;i<N;i++)scanf("%d",&v),ET[PARENT[i]=--v].push_back(i);
        PARENT[0]=N;
        for(int i=0;i<N;i++)COST[i]=TAG[i]=0LL;
        for(int i=0;i<Q;i++)
        {
            auto &q=QUERY[i];
            scanf("%d%lld",&q.first,&q.second),COST[--q.first]+=q.second;
        }
        if(true)
        {
            TOPU.clear();
            queue<int>q;q.push(0);
            while(!q.empty())
            {
                const int u=q.front();q.pop();
                TOPU.push_back(u);
                for(const int nxt:ET[u])q.push(nxt);
            }
            assert((int)TOPU.size()==N);
        }
        for(int i=N-1;i>=0;i--)
        {
            const int u=TOPU[i];
            for(const int nxt:ET[u])COST[u]+=COST[nxt];
        }
        for(int i=0;i<=N;i++)DJ[i]=i;
        int ans=N;
        for(int i=N-1;i>=0;i--)
        {
            const int u=TOPU[i];
            if(COST[u]<K)DJ[u]=PARENT[u],ans--;
        }
        for(int i=Q-1;i>=0;i--)
        {
            ANS[i]=ans;
            const auto &q=QUERY[i];
            int u=Find(q.first);
            TAG[u]+=q.second;
            COST[u]-=q.second;
            while(u!=N&&COST[u]<K)
            {
                const int nxt=Find(PARENT[u]);
                TAG[nxt]+=TAG[u];
                COST[nxt]-=TAG[u];
                u=DJ[u]=nxt,ans--;
            }
        }
        for(int i=0;i<Q;i++)printf("%d\n",ANS[i]);
    }
    return 0;
}