题解：#A1005. 流水面条

使得该路径上的节点加上一个非负值，且该值单调不上升。

注意到一定有解，因为非负值可以取零，所以单点修改是可行的。

对于一个节点 ，它的子节点 代表的子树上的情况一定是互不干扰的，因为 是所有 的 ，所以已经处理的 以下的部分是独立的。

同时 对 的贡献是累加性的。如果以 代表让以 为根的子树符合要求的最小操作次数，那么有 ，这个 的贡献是一定会有的。对于 节点也可能产生新的贡献： 的时候，需要单独对于 节点（或者他的祖先）进行一次新的操作，并且将操作后的值赋得最大。

贪心地进行考虑，我们让子节点加到的位置尽可能地大，那么更有可能满足 的需求。如果比 更大了怎么办？在之前操作的时候在 位置把数值进行突变，总可以在子树情况不变的时候让 的值落在 。这个照应到写代码的时候就是取 操作，这是略去了“操作突变”这个细节的等效结果，对于 的祖先来说。

为什么在合法的时候不让 ？因为这个会增加操作次数，因为求的是 ，这个是划不来的。

总结一下：

1. 多测不清空，爆零两行泪；
2. 十年 一场空，不开 long long 见祖宗 ；
3. 对于叶子节点进行初始化；
4. 求出子节点给的合贡献；
5. 如果子节点不能满足当前的需求，那么对于当前节点单独给贡献，并且更新最大值；
6. 如果子节点的值的和大过了上限，说明之前一系列突变操作让 回到 ；

代码：

#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int MAXN = 200005;

int t, n, st, ed;
int edgeCount;
int head[MAXN], toNode[MAXN], nextEdge[MAXN];
LL l[MAXN], r[MAXN], f[MAXN], maxVal[MAXN];

inline int read() {
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}
inline void addEdge(int from, int to) {
    edgeCount++;
    toNode[edgeCount] = to;
    nextEdge[edgeCount] = head[from];
    head[from] = edgeCount;
    return;
}
inline void dfs(int from) {
    bool isLeaf = true;
    for (int i = head[from]; i; i = nextEdge[i]) {
        isLeaf = false;
        dfs(toNode[i]);
        maxVal[from] += maxVal[toNode[i]];
        f[from] += f[toNode[i]];
    }
    if (isLeaf)
        f[from] = 1, maxVal[from] = r[from];
    if (maxVal[from] < l[from])
        f[from]++, maxVal[from] = r[from];
    maxVal[from] = min(maxVal[from], r[from]);
    return;
}

int main() {
    t = read();
    while (t--) {
        n = read();
        st = ed + 1, ed = ed + n;
        for (int i = st + 1; i <= ed; ++i)
            addEdge(st - 1 + read(), i);
        for (int i = st; i <= ed; ++i)
            l[i] = read(), r[i] = read();
        dfs(st);
        cout << f[st] << '\n';
    }
    return 0;
}