思路与算法

以真实根迭代遍历记录深度，后序为每个节点保存从该节点开始的最终(Alice石数,Bob石数)。当前玩家必须取该节点，而后由另一玩家选孩子：若下一位是Alice，选Bob最少、再Alice最多的孩子结果；若下一位是Bob，选Bob最多、再Alice最少。最后把本节点石数加给当前玩家。

正确性说明

叶节点结果直接确定。假设孩子子游戏结果正确，下一位玩家面对的全部可选策略正好是这些孩子结果；依题目给定的优先级比较，即得到该玩家最优动作。加上当前必取的石数不改变动作之间比较，后序归纳根的二元结果正确。

复杂度

读入、父亲和深度初始化O(N)，树遍历与后序总扫描每边常数次O(N)，空间O(N)。迭代处理10万长链，石数总量使用64位。

易错点

不要让取走当前节点的人同时选择下一堆；下一玩家才选择孩子。两人不是单纯最大化各自石数的对称规则，Alice先最小化Bob，Bob先最大化自己。根不必编号1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> w(n), A(n), B(n);
    for (auto &x : w)
        cin >> x;
    vector<vector<int>> g(n);
    vector<int> par(n, -1), dep(n), ord;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[--u].push_back(--v);
        par[v] = u;
    }
    int root = find(par.begin(), par.end(), -1) - par.begin();
    ord.push_back(root);
    for (size_t i = 0; i < ord.size(); i++)
        for (int v : g[ord[i]]) {
            dep[v] = dep[ord[i]] + 1;
            ord.push_back(v);
        }
    for (int i = n - 1; i >= 0; i--) {
        int u = ord[i];
        if (!g[u].empty()) {
            int best = g[u][0];
            bool nextAlice = dep[u] % 2;
            for (int v : g[u])
                if (nextAlice ? (B[v] < B[best] || (B[v] == B[best] && A[v] > A[best]))
                              : (B[v] > B[best] || (B[v] == B[best] && A[v] < A[best])))
                    best = v;
            A[u] = A[best];
            B[u] = B[best];
        }
        if (dep[u] % 2)
            B[u] += w[u];
        else
            A[u] += w[u];
    }
    cout << A[root] << ' ' << B[root] << '\n';
}