UOJ139 【UER #4】被删除的黑白树 题解

题目链接：#139. 【UER #4】被删除的黑白树

题意：

很久很久以前，有一棵树加入了 UOJ 群。

这天，在它讨论“一棵树应该怎么旋转”的时候一不小心被删除了，变成了被删除的树。

突然间，它突然发现它失去了颜色，变成了一棵纯白的树。这让它感觉很焦躁，于是它来拜托你给自己染上一些颜色。

我们可以把它描述为一棵 $n$ 个节点的有根树（默认树的根为 $1$ 号节点），所有非根的度数为 $1$ 的节点被称为叶子节点。最开始所有的节点都是白色的。

现在你需要选出一些节点并把这些节点染成黑色的。为了迎合树的审美，你的染色方案必须要满足所有叶子节点到根路径上的黑色节点个数相同。

你发现黑色节点个数越多，树就会越高兴，所以你想要知道在所有合法的染色方案中，黑色节点总个数最多是多少。

输入格式：

第一行一个正整数 $n$ 表示树的节点个数。

接下来的 $n-1$ 行，每行是两个整数 $u,v\ (1 \leq u,v \leq n,u \neq v)$ 表示树上的一条边。

输出格式：

一个整数，表示在所有合法方案中黑色节点的最多数量。

贪心，找到层数最高的那个叶子，把这层以上的全部染黑。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

vector<int> vec[N];
int res, mxdep[N];
void dfs(int u, int fa)
{
    int mx = INF;
    for(int v : vec[u]) if(v != fa)
        { dfs(v, u); down(mx, mxdep[v]); }
    mxdep[u] = (mx == INF ? 1 : mx + 1);
}
void dfs(int u, int fa, int dep)
{
    if(mxdep[u] == dep) { ++res, --dep; }
    for(int v : vec[u]) if(v != fa) dfs(v, u, dep);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v); vec[v].push_back(u);
    }
    dfs(1, 0); dfs(1, 0, mxdep[1]); cout << res << '\n';
    return 0;
}

---

参考文献：

[1] https://yhx-12243.github.io/OI-transit/records/uoj139.html