Chaos Slover 补档计划 - 可并堆

2015.11.11 08:04 Wed| 13 visits oi_2016| ChaosSlover补档计划| Text

可并堆

可并堆有很多种类

  • 斜堆(Skew Heap)
  • 左偏树(Leftist Tree)
  • 二项堆(Binomial Heap)
  • 配对堆(Pairing Heap)
  • 斐波那契堆(Fibonacci Heap)

其中斐波那契堆是个神。除了左偏树我都不会写。

BZOJ1455 罗马游戏

可并堆裸题。除此之外用一个数组记录每一个人被没被杀死,再用一个并查集简单维护一下就好了。

我的可并堆模板原来是大根堆呢。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
using namespace std;

#define N 1000005

struct heap
{
    typedef pair<int, int> Tp;
    struct node
    {
        static node *nil;
        node *son[2];
        Tp key; int npl;

        node() : npl(-1) {}
        node(Tp _key) : key(_key), npl(0) { son[0] = son[1] = nil; }
    };

    node *root;

    heap() { root = node::nil; }

    node *merge(node *x, node *y)
    {
        if (x == node::nil) return y;
        if (y == node::nil) return x;
        if (x->key < y->key) swap(x, y);
        x->son[1] = merge(x->son[1], y);
        if (x->son[0]->npl < x->son[1]->npl)
            swap(x->son[0], x->son[1]);
        x->npl = x->son[1]->npl + 1;
        return x;
    }

    inline bool empty() { return root == node::nil; }

    inline Tp top() { return root->key; }

    inline void push(Tp y)
    {
        node *t = new node(y);
        root = merge(root, t);
    }

    inline void pop()
    {
        node *t = merge(root->son[0], root->son[1]);
        delete root;
        root = t;
    }

    inline void insert(heap &x)
    {
        root = merge(root, x.root);
        x.root = node::nil;
    }
};

heap::node *heap::node::nil = new heap::node();

heap q[N];
int n, m, f[N], killed[N];

int find(int x)
{
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}

int main()
{
    cin >> n;
    for (int x, i = 1; i <= n; ++i)
        scanf("%d", &x), q[i].push(make_pair(-x, i));
    for (int i = 1; i <= n; ++i) f[i] = i;
    cin >> m;
    char opt[5];
    for (int x, y, i = 1; i <= m; ++i)
    {
        scanf("%s", opt);
        if (opt[0] == 'M')
        {
            scanf("%d%d", &x, &y);
            if (killed[x] || killed[y]) continue;
            x = find(x), y = find(y);
            if (x != y) q[x].insert(q[y]), f[y] = x;
        }
        else
        {
            scanf("%d", &x);
            if (killed[x])
                { printf("0\n"); continue; }
            x = find(x);
            pair<int, int> p = q[x].top(); q[x].pop();
            printf("%d\n", -p.first); killed[p.second] = 1;
        }
    }
    return 0;
}

BZOJ2809 [Apio2012]dispatching

这道题的关键就在于如何求每一棵子树内的权值最小的几个结点,使得它们的权值和不大于 M。

可以对于某一个父亲结点,使用可并堆把子结点选中的点合并起来,再加入自身。每一次弹掉权值最大的点,直到堆里的结点的权值和不大于 M 为止。

时间复杂度:对于堆的插入和弹出最多都只进行 N 次,合并进行了 N-1 次,总复杂度 O(NlogN)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

#define N 100005

struct heap
{
    typedef int Tp;
    struct node
    {
        static node *nil;
        node *son[2];
        Tp key; int npl, size;

        node() : npl(-1), size(0) {}
        node(Tp _key) : key(_key), npl(0), size(1) { son[0] = son[1] = nil; }
    };

    node *root;

    heap() { root = node::nil; }

    node *merge(node *x, node *y)
    {
        if (x == node::nil) return y;
        if (y == node::nil) return x;
        if (x->key < y->key) swap(x, y);
        x->son[1] = merge(x->son[1], y);
        if (x->son[0]->npl < x->son[1]->npl)
            swap(x->son[0], x->son[1]);
        x->npl = x->son[1]->npl + 1;
        x->size = x->son[0]->size + x->son[1]->size + 1;
        return x;
    }

    inline bool empty() { return root == node::nil; }

    inline int size() { return root->size; }

    inline Tp top() { return root->key; }

    inline void push(Tp y)
    {
        node *t = new node(y);
        root = merge(root, t);
    }

    inline void pop()
    {
        node *t = merge(root->son[0], root->son[1]);
        delete root;
        root = t;
    }

    inline void insert(heap &x)
    {
        root = merge(root, x.root);
        x.root = node::nil;
    }
};

heap::node *heap::node::nil = new heap::node();

heap q[N];
vector<int> son[N];
int n, m, b[N], c[N], l[N];
long long sum[N], ans;

void dfs(int x)
{
    q[x].push(c[x]); sum[x] = c[x];
    for (int i = 0; i < (int)son[x].size(); ++i)
        dfs(son[x][i]);
    while (sum[x] > m)
        sum[x] -= q[x].top(), q[x].pop();
    ans = max(ans, 1ll * l[x] * q[x].size());
    sum[b[x]] += sum[x]; q[b[x]].insert(q[x]);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d", &b[i], &c[i], &l[i]),
        son[b[i]].push_back(i);
    dfs(1);
    cout << ans << endl;
    return 0;
}

BZOJ3011 [Usaco2012 Dec]Running Away From the Barn

和上面一道题思路十分相似。需要在可并堆上打标记,这个也很好实现。非常好实现。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;

#define N 200005

struct heap
{
    typedef long long Tp;
    struct node
    {
        static node *nil;
        node *son[2];
        Tp key, tag; int npl, size;

        node() : npl(-1), size(0) {}
        node(Tp _key)
        : key(_key), tag(0), npl(0), size(1) { son[0] = son[1] = nil; }

        void pushdown()
        {
            son[0]->key += tag; son[1]->key += tag;
            son[0]->tag += tag; son[1]->tag += tag; tag = 0;
        }
    };

    node *root;

    heap() { root = node::nil; }

    node *merge(node *x, node *y)
    {
        if (x == node::nil) return y;
        if (y == node::nil) return x;
        if (x->key < y->key) swap(x, y);
        x->pushdown();
        x->son[1] = merge(x->son[1], y);
        if (x->son[0]->npl < x->son[1]->npl)
            swap(x->son[0], x->son[1]);
        x->npl = x->son[1]->npl + 1;
        x->size = x->son[0]->size + x->son[1]->size + 1;
        return x;
    }

    inline bool empty() { return root == node::nil; }

    inline int size() { return root->size; }

    inline Tp top() { return root->key; }

    inline void push(Tp y)
    {
        node *t = new node(y);
        root = merge(root, t);
    }

    inline void pop()
    {
        root->pushdown();
        node *t = merge(root->son[0], root->son[1]);
        delete root;
        root = t;
    }

    inline void insert(heap &x)
    {
        root = merge(root, x.root);
        x.root = node::nil;
    }

    inline void add(Tp x)
    {
        root->key += x;
        root->tag += x;
    }
};

heap::node *heap::node::nil = new heap::node();

heap q[N];
vector<int> son[N];
int n, p[N], ans[N];
long long l, v[N];

void dfs(int x)
{
    for (int i = 0; i < (int)son[x].size(); ++i)
        dfs(son[x][i]);
    q[x].push(0);
    while (!q[x].empty() && q[x].top() > l) q[x].pop();
    ans[x] = q[x].size();
    q[x].add(v[x]); q[p[x]].insert(q[x]);
}

int main()
{
    cin >> n >> l;
    for (int i = 2; i <= n; ++i)
        scanf("%d%lld", &p[i], &v[i]),
        son[p[i]].push_back(i);
    dfs(1);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

BZOJ2333 [SCOI2011]棘手的操作

刘老师说:在结构体里面的 inline 都是没用的……

维护喜闻乐见的一大堆操作。其中联通块相关的操作都用可并堆处理。把所有可并堆堆顶的权值都扔进平衡树(multiset)里面,就可以支持询问最大权值了。

以下具体操作(orz HZWER)

  • U 把 x、y 所在堆顶删出 set。合并两个堆,把堆顶加进 set;
  • A1 (最麻烦)处理 x 祖先的标记,把 x 所在堆顶删出 set,把 x 从堆中取出,加完 v 再放进去,堆顶加入 set;
  • A2 x 所在堆顶删出 set,打标记改权值后堆顶放回 set;
  • A3 开个变量存起来;
  • F1 处理 x 祖先的标记,输出;
  • F2 输出 x 所在堆顶;
  • F3 输出 set 中最大值。

其中 A1和 F1 操作需要直接查询和删除特定的一个结点。由于堆的性质,我们不能直接从堆顶向下找,而需要弄一个数组指向每一个结点。然后这就会产生一大堆细节……写删除的时候一定要小心,连好每一个儿子和父亲,尤其是对于那些写指针的人……

以下口胡,不保证正确性:

我们在删除一个结点的时候,很可能整个堆就不满足左偏树性质了。可是,大概偏差并不是特别大【毕竟删除之后结点数变少了嘛】,所以能过所有的测试数据。

另外其实左偏树并不平衡,所以祖先链上的标记都下传的话可能会很费事。然而并没有被卡。

这道题还有离线线段树做法:预处理出 DFS 序什么的,将连通的结点放在线段树的相近位置,之后就可以进行区间修改什么的了(并不是很明白)……

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <bits/stdc++.h>
using namespace std;

#define N 300005

struct heap
{
    typedef int Tp;
    struct node
    {
        static node *nil;
        node *fa, *son[2];
        Tp key, tag; int npl, size;

        node() : npl(-1), size(0) {}
        node(Tp _key) : key(_key), tag(0), npl(0), size(1)
        { fa = son[0] = son[1] = nil; }

        void pushdown()
        {
            son[0]->key += tag; son[0]->tag += tag;
            son[1]->key += tag; son[1]->tag += tag; tag = 0;
        }
    };

    node *root;

    heap() { root = node::nil; }

    node *merge(node *x, node *y)
    {
        if (x == node::nil) return y;
        if (y == node::nil) return x;
        if (x->key < y->key) swap(x, y);
        x->pushdown();
        x->son[1] = merge(x->son[1], y);
        x->son[1]->fa = x;
        if (x->son[0]->npl < x->son[1]->npl)
            swap(x->son[0], x->son[1]);
        x->npl = x->son[1]->npl + 1;
        x->size = x->son[0]->size + x->son[1]->size + 1;
        return x;
    }

    bool empty() { return root == node::nil; }

    int size() { return root->size; }

    Tp top() { return root->key; }

    void push(node *x)
    {
        root = merge(root, x);
    }

    void pop(node *x)
    {
        get(x);
        node *k = x->fa;
        node *t = merge(x->son[0], x->son[1]);
        if (k == node::nil) root = t;
        else if (x == k->son[0]) k->son[0] = t;
        else k->son[1] = t;
        t->fa = k;
        x->fa = x->son[0] = x->son[1] = node::nil;
    }

    void insert(heap &x)
    {
        root = merge(root, x.root);
        x.root = node::nil;
    }

    void add(Tp x)
    {
        root->key += x; root->tag += x;
    }

    void get(node *t)
    {
        if (t->fa != node::nil)
            get(t->fa);
        t->pushdown();
    }
};

heap::node *heap::node::nil = new heap::node();
heap q[N]; heap::node *p[N];

int n, m, f[N], tot;
multiset<int> s;

int find(int x)
{
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}

int main()
{
    cin >> n;
    for (int x, i = 1; i <= n; ++i)
        scanf("%d", &x), p[i] = new heap::node(x);
    for (int i = 1; i <= n; ++i)
        q[i].push(p[i]), s.insert(p[i]->key), f[i] = i;
    cin >> m;
    char opt[5];
    for (int x, y, i = 1; i <= m; ++i)
    {
        scanf("%s", opt);
        if (opt[0] == 'U')
        {
            scanf("%d%d", &x, &y);
            x = find(x); y = find(y);
            if (x == y) continue;
            s.erase(s.lower_bound(q[x].top()));
            s.erase(s.lower_bound(q[y].top()));
            q[x].insert(q[y]), f[y] = x;
            s.insert(q[x].top());
        }
        else if (opt[0] == 'A')
        {
            if (opt[1] == '1')
            {
                scanf("%d%d", &x, &y);
                int fx = find(x);
                s.erase(s.lower_bound(q[fx].top()));
                q[fx].pop(p[x]); p[x]->key += y; q[fx].push(p[x]);
                s.insert(q[fx].top());
            }
            else if (opt[1] == '2')
            {
                scanf("%d%d", &x, &y);
                int fx = find(x);
                s.erase(s.lower_bound(q[fx].top()));
                q[fx].add(y);
                s.insert(q[fx].top());
            }
            else
            {
                scanf("%d", &x); tot += x;
            }
        }
        else
        {
            if (opt[1] == '1')
            {
                scanf("%d", &x);
                int fx = find(x);
                q[fx].get(p[x]);
                printf("%d\n", p[x]->key + tot);
            }
            else if (opt[1] == '2')
            {
                scanf("%d", &x);
                x = find(x);
                printf("%d\n", q[x].top() + tot);
            }
            else
            {
                printf("%d\n", *s.rbegin() + tot);
            }
        }
    }
    return 0;
}

BZOJ1367 [Baltic2004]sequence

那些写题解说这道题是裸裸的左偏树的真是够了。

大概可以观察出,答案序列会被分成很多段,其中每一段上的答案相同,都是 t 序列在这一段上的中位数。还要保证每一段都不能被分成两小段,使得前一小段中 t 序列的中位数小于后一小段中 t 序列的中位数(否则把这一段拆开,答案更优)。这里给出了一个证明(虽然我并没有十分看懂)。

具体做法就是我们需要从前往后依次加入 t 序列中每一个数,把它看作单独一个区间。每当当前区间的中位数小于前一个区间的中位数时,就将两段区间合并。这样维护一个中位数递增的单调栈,最终我们就会求出来一个单调不下降的答案序列。

然而我们要求的是上升答案序列?只需要最开始把 t 序列的第 i 项的值减去 i 就好了。

上述求区间中位数和合并的操作都可以用可并堆做。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

#define N 1000005

struct heap
{
    typedef int Tp;
    struct node
    {
        static node *nil;
        node *son[2];
        Tp key; int npl, size;

        node() : npl(-1), size(0) {}
        node(int _key) : key(_key), npl(0), size(1) { son[0] = son[1] = nil; }
    };

    node *root;

    heap() { root = node::nil; }

    node *merge(node *x, node *y)
    {
        if (x == node::nil) return y;
        if (y == node::nil) return x;
        if (x->key < y->key) swap(x, y);
        x->son[1] = merge(x->son[1], y);
        if (x->son[0]->npl < x->son[1]->npl)
            swap(x->son[0], x->son[1]);
        x->npl = x->son[1]->npl + 1;
        x->size = x->son[0]->size + x->son[1]->size + 1;
        return x;
    }

    bool empty() { return root == node::nil; }

    int size() { return root->size; }

    Tp top() { return root->key; }

    void push(Tp x)
    {
        node *t = new node(x);
        root = merge(root, t);
    }

    void pop()
    {
        node *t = merge(root->son[0], root->son[1]);
        delete root;
        root = t;
    }

    void insert(heap &x)
    {
        root = merge(root, x.root);
        x.root = node::nil;
    }
};

heap::node *heap::node::nil = new heap::node();

int n, a[N];
long long ans;
stack<heap> sq;
stack<int> sl;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]), a[i] -= i;
    for (int i = 1; i <= n; ++i)
    {
        heap h; int tl = i;
        h.push(a[i]);
        while (!sq.empty() && h.top() < sq.top().top())
        {
            h.insert(sq.top()); sq.pop();
            tl = sl.top(); sl.pop();
            while (h.size() > (i - tl + 2) / 2) h.pop();
        }
        sq.push(h); sl.push(tl);
    }
    for (int i = n; i; --i)
    {
        ans += abs(a[i] - sq.top().top());
        if (i == sl.top()) sq.pop(), sl.pop();
    }
    cout << ans << endl;
    return 0;
}

BZOJ2006 [NOI2010]超级钢琴

并不需要可并堆。挖坑待填。

CH round1 OVOO

不幸的是,CH 挂掉了。于是我的程序仅仅是和 @140142 对拍正确的。

Upd:2016/1/5

CH 的这道题竟然活了——然后我就 AC 了。

140142的题解里面还画了几张很好理解的图,好评。用 priority_queue<pair<long long, heap<int, int> > > 记录答案,其中 heap<int, int> 中记录的分别是一条边的边权和会到达的结点。priority_queue 中记录的分别是答案和包含下一次可能会横向拓展到的边的堆。

至于可持久化可并堆的实现方式,就是在合并的时候在一个新结点上进行操作,具体代码实现和普通的可并堆相差无几。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

#define N 100005

struct heap
{
    typedef pair<int, int> Tp;
    struct node
    {
        static node *nil;
        node *son[2];
        Tp key; int npl, size;

        node() : npl(-1), size(0) {}
        node(Tp _key) : key(_key), npl(0), size(1) { son[0] = son[1] = nil; }
    };

    bool operator <(const heap &x) const { return top() < x.top(); }

    node *root;

    heap() { root = node::nil; }

    node *merge(node *x, node *y)
    {
        if (x == node::nil) return y;
        if (y == node::nil) return x;
        if (x->key < y->key) swap(x, y);
        node *p = new node(); *p = *x;
        p->son[1] = merge(p->son[1], y);
        if (p->son[0]->npl < p->son[1]->npl)
            swap(p->son[0], p->son[1]);
        p->npl = p->son[1]->npl + 1;
        p->size = p->son[0]->size + p->son[1]->size + 1;
        return p;
    }

    bool empty() { return root == node::nil; }

    int size() { return root->size; }

    Tp top() const { return root->key; }

    void push(Tp x)
    {
        node *t = new node(x);
        root = merge(root, t);
    }

    void pop()
    {
        root = merge(root->son[0], root->son[1]);
    }

    void insert(heap &x)
    {
        root = merge(root, x.root);
    }
};

heap::node *heap::node::nil = new heap::node();
heap h[N], temp;
priority_queue<pair<long long, heap> > q;
int n, k; long long ans;

int main()
{
    cin >> n >> k;
    h[0].push(make_pair(0, 1));
    for (int x, y, i = 2; i <= n; ++i)
    {
        scanf("%d%d", &x, &y);
        h[x].push(make_pair(-y, i));
    }
    q.push(make_pair(0, h[0]));
    for (int i = 1; i <= k; ++i)
    {
        if (q.empty()) break;
        ans = q.top().first;
        heap ovoo = q.top().second;
        q.pop();
        pair<int, int> t = ovoo.top();
        ovoo.pop();
        if (!ovoo.empty())
            q.push(make_pair(ans - t.first + ovoo.top().first, ovoo));
        ovoo.insert(h[t.second]);
        if (!ovoo.empty())
            q.push(make_pair(ans + ovoo.top().first, ovoo));
    }
    cout << (-ans) % 998244353 << endl;
    return 0;
}

BZOJ4003 [JLOI2015]城池攻占

可并堆 + 双标记。裸题 = = 注意神奇的 long long 问题。

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;

#define N 300005

struct heap
{
    typedef pair<long long, int> Tp;
    struct node
    {
        static node *nil;
        node *son[2];
        Tp key; long long tag1, tag2; int npl, size;

        node() : npl(-1), size(0) {}
        node(Tp _key) : key(_key), tag1(1), tag2(0), npl(0), size(1)
        { son[0] = son[1] = nil; }
        void pushdown()
        {
            son[0]->key.first *= tag1; son[1]->key.first *= tag1;
            son[0]->tag1 *= tag1; son[1]->tag1 *= tag1;
            son[0]->tag2 *= tag1; son[1]->tag2 *= tag1;
            son[0]->key.first += tag2; son[1]->key.first += tag2;
            son[0]->tag2 += tag2; son[1]->tag2 += tag2;
            tag1 = 1; tag2 = 0;
        }
    };

    node *root;

    heap() { root = node::nil; }

    node *merge(node *x, node *y)
    {
        if (x == node::nil) return y;
        if (y == node::nil) return x;
        if (x->key > y->key) swap(x, y);
        x->pushdown();
        x->son[1] = merge(x->son[1], y);
        if (x->son[0]->npl < x->son[1]->npl)
            swap(x->son[0], x->son[1]);
        x->npl = x->son[1]->npl + 1;
        x->size = x->son[0]->size + x->son[1]->size + 1;
        return x;
    }

    int size() { return root->size; }

    bool empty() { return root == node::nil; }

    Tp top() { return root->key; }

    void push(Tp x)
    {
        node *t = new node(x);
        root = merge(root, t);
    }

    void pop()
    {
        root->pushdown();
        node *t = merge(root->son[0], root->son[1]);
        delete root;
        root = t;
    }

    void insert(heap x)
    {
        root = merge(root, x.root);
        x.root = node::nil;
    }

    void maketag(long long x, long long y)
    {
        root->pushdown();
        root->key.first *= x; root->key.first += y;
        root->tag1 = x; root->tag2 = y;
    }
};

heap::node *heap::node::nil = new heap::node();
heap q[N];
long long n, m, head[N], f[N], a[N], c[N];
int deep[N], ans1[N], ans2[N]; long long h[N], v[N], s[N];

struct graph
{
    int next, to;
    graph() {}
    graph(int _next, int _to)
    : next(_next), to(_to) {}
} edge[N];

inline void add(int x, int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x], y);
    head[x] = cnt;
}

void dfs(int x)
{
    deep[x] = deep[f[x]] + 1;
    for (int i = head[x]; i; i = edge[i].next)
        dfs(edge[i].to);
    while (!q[x].empty() && q[x].top().first < h[x])
        ans2[q[x].top().second] = x, ++ans1[x], q[x].pop();
    if (q[x].empty()) return;
    if (!a[x]) q[x].maketag(1, v[x]);
    else q[x].maketag(v[x], 0);
    q[f[x]].insert(q[x]);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &h[i]);
    for (int i = 2; i <= n; ++i)
        scanf("%d%d%lld", &f[i], &a[i], &v[i]),
        add(f[i], i);
    for (int i = 1; i <= m; ++i)
        scanf("%lld%d", &s[i], &c[i]),
        q[c[i]].push(make_pair(s[i], i));
    dfs(1);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", ans1[i]);
    for (int i = 1; i <= n; ++i)
        printf("%d\n", deep[c[i]] - deep[ans2[i]]);
    return 0;
}