Description：

用 $ m $ 个骑士攻占 $ n $ 个城池。除 $ 1 $ 号城池外，城池 $ i $ 会受到另一座城池 $ f_i $ 的管辖，其中 $ f_i <i$ 。每个城池有一个防御值 $h_i$ ，如果一个骑士的战斗力大于等于城池的生命值，那么骑士就可以占领这座城池；否则占领失败，骑士将在这座城池牺牲。占领一个城池以后，骑士的战斗力将发生变化加上一个值或乘上一个值 $(>0)$ ，然后继续攻击管辖这座城池的城池，直到占领 $ 1 $ 号城池，或牺牲为止。问对于每个城池，输出有多少个骑士在这里牺牲；对于每个骑士，输出他攻占的城池数量。

$1\le n,m \le 3\times 10^5$

Solution：

$dfs$ 遍历每个点，将儿子节点中所有还活着的骑士加到这个点上来，删掉牺牲的骑士并修改战斗力，注意到战斗力变化并不会影响到先对战斗力强弱，于是可以整体打标记，需要一个支持删除最值，合并，打标记的 $log_2n$ 数据结构 $\Longrightarrow$ 左偏树。

注意合并两个儿子前先 $pushdown$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 300010

typedef long long ll;

ll def[MAXN],cha[MAXN],lev[MAXN];

int man[MAXN];

ll po[MAXN];

int st[MAXN];

struct node

{

    int lc,rc,d,f;

    ll val,add,mul;

    node(){lc = rc = d = f = 0;val = add = 0ll;mul = 1ll;}

}t[MAXN];

int find(int x){return (t[x].f == 0 ? x : find(t[x].f));}

int root[MAXN];

void pushdown(int rt)

{

    if(t[rt].lc != 0)

    {

        t[t[rt].lc].val = t[t[rt].lc].val * t[rt].mul + t[rt].add;

        t[t[rt].lc].mul = t[t[rt].lc].mul * t[rt].mul;

        t[t[rt].lc].add = t[t[rt].lc].add * t[rt].mul + t[rt].add;

    }

    if(t[rt].rc != 0)

    {

        t[t[rt].rc].val = t[t[rt].rc].val * t[rt].mul + t[rt].add;

        t[t[rt].rc].mul = t[t[rt].rc].mul * t[rt].mul;

        t[t[rt].rc].add = t[t[rt].rc].add * t[rt].mul + t[rt].add;

    }

    t[rt].mul = 1ll;t[rt].add = 0ll;

    return;

}

int merge(int a,int b)

{

    if(a == 0)return b;if(b == 0)return a;

    if(t[a].val > t[b].val)swap(a,b);

    pushdown(a);

    t[a].rc = merge(t[a].rc,b);

    if(t[a].rc != 0)t[t[a].rc].f = a;

    if(t[t[a].lc].d < t[t[a].rc].d)swap(t[a].lc,t[a].rc);

    if(t[a].rc == 0)t[a].d = 0;

    else t[a].d = t[t[a].rc].d + 1;

    return a;

}

struct edge

{

    int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

inline void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    return;

}

int dep[MAXN];

int ans1[MAXN],ans2[MAXN];

void dfs(int k)

{

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        dep[e[i].to] = dep[k] + 1;

        dfs(e[i].to);

        root[k] = merge(root[k],root[e[i].to]);

    }

    while(root[k] != 0 && t[root[k]].val < def[k])

    {

        ans2[root[k]] = dep[st[root[k]]] - dep[k];

        pushdown(root[k]);

        root[k] = merge(t[root[k]].lc,t[root[k]].rc);

        ++ans1[k];

    }

    if(cha[k] == 0)

    {

        t[root[k]].val += lev[k];

        t[root[k]].add += lev[k];

    }

    else

    {

        t[root[k]].val *= lev[k];

        t[root[k]].mul *= lev[k];

        t[root[k]].add *= lev[k];

    }

    return;

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)scanf("%lld",&def[i]);

    for(int i = 2;i <= n;++i)scanf("%d%lld%lld",&man[i],&cha[i],&lev[i]);

    for(int i = 2;i <= n;++i)add(man[i],i);

    for(int i = 1;i <= m;++i)scanf("%lld%d",&po[i],&st[i]);

    for(int i = 1;i <= m;++i)t[i].val = po[i];

    for(int i = 1;i <= m;++i)root[st[i]] = merge(root[st[i]],i);

    add(0,1);def[0] = 0x3f3f3f3f3f3f3f3f;

    dfs(0);

    for(int i = 1;i <= n;++i)printf("%d\n",ans1[i]);

    for(int i = 1;i <= m;++i)printf("%d\n",ans2[i]);

    return 0;

}