树的染色补题记录

树的染色

Description
给你一颗二叉树，以1号节点为根。每次操作可以选择一个点，将该点、该点的父亲、该点的左右儿子染色。问至少多少次操作后能将所有节点全部染色。

Input
第一行输入一个正整数 NN 表示树的节点树。 (1 <= N <= 100000)(1<=N<=100000)
接下来 N - 1N−1 行，每行两个正整数 u、vu、v，表示节点 uu 和 vv 之间存在一条边。 (编号从 11 开始)

Output
输出一个整数，表示最少的操作次数。

Sample
Input
5
1 2
2 3
2 4
3 5
Output
2

思路：贪心，如果这个点是树的最底层，那么它一定要被染色。因为只要最底层都被染色了，那么相当于最底层不用被考虑。那么它的上一层就会被当成最底层。进而思考如何实现所有最底层被染色，则思考出对未被染色的父节点操作最快。也就是每次对未被染色的点的父节点进行操作，当这一层所有点的父节点被染色，这一层必然全部染色。

上代码：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N = 1e5 + 10;

int n, ans;
bool flag[N];
vector<int> nxt[N];

void choose(int u)
{
    ans++;
    flag[u] = 1;
    for(auto v : nxt[u]) flag[v] = 1;
}

void DFS(int u, int f)
{
    for(auto v : nxt[u])
    {
        if(v == f) continue;
        DFS(v, u);
    }

    if(flag[u] == 0) choose(f);
}

int main()
{
    cin >> n;
    for(int i = 1 ; i < n ; i++)
    {
        int u, v;
        cin >> u >> v;
        nxt[u].push_back(v);
        nxt[v].push_back(u);
    }
    DFS(1, 0);
    cout << ans << endl;
    return 0;
}

最后

以上就是孤独白昼为你收集整理的树的染色补题记录的全部内容，希望文章能够帮你解决树的染色补题记录所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。