题意

给你n个节点的树，让你给每个节点进行赋值，并且赋的值需要为正整数；
同时当一个节点的值等于所有邻居节点的值的和时，这个点为好点；
求出一组赋值情况，满足树的好点个数最大化的同时，所有节点赋值的总和最小；

思路

代码

#include<bits/stdc++.h>

using namespace std;
vector<int> g[200005];
int f[200005][2][2];
long long ans[200005];
int cnt[200005];

void dp(int x, int fa) {
    f[x][1][0] = 1;//好点个数
    f[x][1][1] = g[x].size();//累计
    f[x][0][0] = 0;
    f[x][0][1] = 1;
    for (auto k: g[x]) {
        if (k == fa)continue;
        dp(k, x);
    }
    for (auto k: g[x]) {
        if (k == fa)continue;
        f[x][1][0] += (f[k][0][0]);
        f[x][1][1] += (f[k][0][1]);
    }
    for (auto k: g[x]) {
        if (k == fa)continue;
        if (f[k][0][0] > f[k][1][0]) {
            f[x][0][0] += f[k][0][0];
            f[x][0][1] += f[k][0][1];
        } else if (f[k][0][0] == f[k][1][0]) {
            f[x][0][0] += f[k][0][0];
            f[x][0][1] += min(f[k][0][1], f[k][1][1]);
        } else {
            f[x][0][0] += f[k][1][0];
            f[x][0][1] += f[k][1][1];
        }
    }
}

void down(int x, int fa, int now) {
    ans[x] = now;
    if (now == 1) {
        for (auto k: g[x]) {
            if (k == fa)continue;
            down(k, x, 0);
        }
    } else {
        for (auto k: g[x]) {
            if (k == fa)continue;
            if (f[k][0][0] > f[k][1][0]) {
                down(k, x, 0);
            } else if (f[k][0][0] == f[k][1][0]) {
                if (f[k][0][1] < f[k][1][1])
                    down(k, x, 0);
                else
                    down(k, x, 1);
            } else {
                down(k, x, 1);
            }
        }
    }
}

void run() {
    int n;
    cin >> n;
//    for (int i = 1; i <= n; i++)g[i].clear(), f[i] = 0, ans[i] = 0;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].emplace_back(y);
        g[y].emplace_back(x);
    }
    if (n == 2) {
        cout << 2 << ' ' << 2 << '\n';
        cout << 1 << ' ' << 1 << '\n';
        return;
    }
    dp(1, 0);
    bool flag = 1;
    if (f[1][0][0] > f[1][1][0])flag = 0;
    if (f[1][0][0] == f[1][1][0] && f[1][0][1] < f[1][1][1])flag = 0;
    down(1, 0, flag);
    cout << f[1][flag][0] << ' ' << f[1][flag][1] << '\n';
    for (int i = 1; i <= n; i++) {
        if (ans[i])cout << g[i].size() << ' ';
        else cout << 1 << ' ';
    }
}

int main() {
    run();
    return 0;
}