果园巡查

思路与复杂度

先迭代遍历获得父在子前的顺序，再逆序处理。节点数量为1加左右子树数量，果实总数为自身果实加左右子树总数。0号空节点的两项均为0。时间和空间 O(n)，用64位整数累计，迭代实现避免20万层递归栈溢出。

正确性与边界

从叶到根归纳，左右子树不重叠且与当前节点一起构成整棵子树。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

long long a[N];
long long sumv[N];
int leftSon[N], rightSon[N];
int cnt[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        cin >> leftSon[i] >> rightSon[i];
    }

    vector<int> order;
    stack<int> st;
    st.push(1);

    while (!st.empty()) {
        int u = st.top();
        st.pop();

        order.push_back(u);

        if (leftSon[u] != 0) {
            st.push(leftSon[u]);
        }
        if (rightSon[u] != 0) {
            st.push(rightSon[u]);
        }
    }

    reverse(order.begin(), order.end());

    for (int u : order) {
        cnt[u] = 1;
        sumv[u] = a[u];

        if (leftSon[u] != 0) {
            cnt[u] += cnt[leftSon[u]];
            sumv[u] += sumv[leftSon[u]];
        }

        if (rightSon[u] != 0) {
            cnt[u] += cnt[rightSon[u]];
            sumv[u] += sumv[rightSon[u]];
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << cnt[i] << " " << sumv[i] << "\n";
    }

    return 0;
}