思路与算法

树中同色诱导子图都是森林，所以同色分量数等于该色点数减该色边数。整理可得最终红分量减蓝分量=Σ红点(2-deg(v))-1。将各点权2-deg降序排序，Alice取第1、3、5…项的和，最后减1。

正确性说明

对红蓝点数及边数计数，用全部边数n-1及红点度数和消去异色边，即得公式。游戏变成双方轮流从固定权值集合取数，只有Alice取到的权进入收益。Alice每次取最大，保证至少获得排序奇数位之和；Bob每次取最大则保证Alice至多该和，可用相邻成对交换或归纳证明。因此排序值为极小极大值。

复杂度

读边及度数初始化O(n)，排序O(nlogn)，求和O(n)，空间O(n)。

易错点

输入小节误写N行边，树必为N-1边，公开两例也如此，包内已说明。叶子有正权，高度点可能负权；不能只取正值，因为Alice每轮必须取点，不能放弃操作。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> d(n, 2);
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        d[u - 1]--;
        d[v - 1]--;
    }
    sort(d.rbegin(), d.rend());
    long long ans = -1;
    for (int i = 0; i < n; i += 2)
        ans += d[i];
    cout << ans << '\n';
}