Gym102896 C - Color the Tree

博主： spirit
发布时间：2021 年 03 月 13 日
1587 次浏览
暂无评论
3417字数
分类： VJ训练赛图论

# [C - Color the Tree](https://codeforces.com/gym/102896/problem/C)

## 题意

给出一个 $n$ 个节点的树，节点可以被染成红色或者绿色。最初的时候该树只有树根（节点 $1$ ）为红色，其他点均为绿色。这棵树必须时刻满足以下要求：

- 树根一定为红色。
- 对于任意一个节点 $p$ ，若点 $p$ 的颜色为红色，则由根节点到点 $p$ 的最短路径上必须满足每一个节点都被染成红色。

接下来你可以对树进行操作，每次操作选定一个节点，将其颜色反转（红变绿，绿变红）。但操作过程有一个要求：

- 将整棵树的染色情况视为树的状态，则树的任何一种状态都至多出现一次。

现在要求你给出一个最长的操作序列，先输出序列长度，然后按照顺序给出每次反转了哪个节点的颜色。

## 思路

1. 首先要解决第一个问题，对于一个给定的树，到底有多少种染色的状态？根据组合计数乘法原理和加法原理，假设根节点为 $root$ ，它的子树的根节点为 $p_1, p_2, p_3 ··· p_m$ ，对应的子树状态数量为 $q_1, q_2, q_3, ··· q_m$ ，那么以 $root$ 为根节点的这棵树的状态数量为 $\prod_{i = 1}^{m} p_i + 1$ 。结论显然，不做证明。
2. 有了树的状态之后，我们还需要考虑一个问题，如何把这些状态连成一条链？在操作序列中，每一次操作其实都是从一个状态到另一个状态的转移，只要我们可以按照这种关系将所有状态串成一条链，这道题就解决了。在数字电路和之前的题目中有过对格雷码的应用，格雷码就是一种两两之间只有一位不同的二进制码。如果我们能用数字表示每个树的状态，令相邻两个状态之间的状态码只相差一位即可，不过这里的状态码要比二进制稍微复杂一些。
3. 接下来我们考虑如何用代码实现上述算法的问题。举个例子，在最后一个样例中，我们有下面这样一颗树：
   
   ![](https://i.loli.net/2021/03/13/W8U9eiu6sgxLKdb.png)
   
   在这个树中，左子树有 $3$ 种状态，右子树有 $3$ 种状态，那么整棵树有 $10$ 种状态，应该需要变化 $9$ 次，但初始状态中点 $1$ 已经被染成红色，故答案序列长度为 $8$ 。如果只用树 $1$ 的状态码来表示上述算法，就是 $1 - 2, 2 - 3, 3 - 4, ··· 8 - 9$ ，显然这对求出答案帮助不大。但是如果将树 $1$ 视为 节点 $1$ 、树 $2$ 和树 $3$ ，用它们的状态码来表述上述过程，是 $100 - 101$，$101 - 102$ ，$102 - 112$ ，$112 - 111$ ，$111 - 110$ ，$110 - 120$ ，$120 - 121$ ，$121 - 122$ ，共 $8$ 个变化过程。同样的，用子树的子树的状态码来表示子树的状态，也是同样的过程，递归操作即可。
4. 最后一步，如何从这个过程中找出答案呢？在上一步中，对于状态码 $101$ ，表达的意思为：根节点 $1$ 的状态为已染成红色，子树 $2$ 的状态码为 $0$  ，子树 $3$ 的状态码为 $1$ ，即首位状态码表示根节点的染色情况，如果该位置从 $0$ 变化到 $1$ ，或者从 $1$ 变化到 $0$ （对应的就是树 $1$ 的状态码由 $0 - 1$ ，$1 - 0$ 的过程），说明我们对节点 $1$ 进行了操作，在操作序列中添加即可。整个的代码逻辑就是对上述过程的递归实现。

## 实现

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define lowbit(x) (x & -x)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0), eps = 1e-6;
const int N = 2e6 + 10;
struct Node {
    int id, sum, val;
    bool flag;
    vector<int> child;
} tr[25];
int ans[N], cnt;

void get_sum(int p) {
    int num = 1;
    for (auto it : tr[p].child) {
        get_sum(it);
        num *= tr[it].sum;
    }
    tr[p].sum = num + 1;
}

bool change(int p) {
    if (tr[p].flag) {
        if (tr[p].val == 0) {
            tr[p].flag = false;
            return false;
        } else if (tr[p].val == 1) {
            tr[p].val--;
            ans[++cnt] = tr[p].id;
        } else {
            tr[p].val--;
            bool f = true;
            while (f) {
                for (int i = 0; i < tr[p].child.size(); i++)
                    if (change(tr[p].child[i])) {
                        f = false;
                        break;
                    }
            }
        }
    } else {
        if (tr[p].val == tr[p].sum - 1) {
            tr[p].flag = true;
            return false;
        } else if (tr[p].val == 0) {
            tr[p].val++;
            ans[++cnt] = tr[p].id;
        } else {
            tr[p].val++;
            bool f = true;
            while (f) {
                for (int i = 0; i < tr[p].child.size(); i++)
                    if (change(tr[p].child[i])) {
                        f = false;
                        break;
                    }
            }
        }
    }
    return true;
}

int main(int argc, char const *argv[]) {
    int n, u;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        tr[i].id = i;
        scanf("%d", &u);
        tr[u].child.push_back(i);
    }
    get_sum(1);
    tr[1].val++;
    for (int i = 1; i < tr[1].sum; i++) {
        change(1);
    }
    printf("%d\n", cnt);
    for (int i = 1; i <= cnt; i++)
        printf("%d%c", ans[i], i == cnt ? '\n' : ' ');
    return 0;
}
```

最后修改：2021 年 03 月 16 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Gym102896 C - Color the Tree

spirit • 2021 年 03 月 13 日

# [C - Color the Tree](https://codeforces.com/gym/102896/problem/C)

## 题意

- 树根一定为红色。
- 对于任意一个节点 $p$ ，若点 $p$ 的颜色为红色，则由根节点到点 $p$ 的最短路径上必须满足每一个节点都被染成红色。

接下来你可以对树进行操作，每次操作选定一个节点，将其颜色反转（红变绿，绿变红）。但操作过程有一个要求：

- 将整棵树的染色情况视为树的状态，则树的任何一种状态都至多出现一次。

现在要求你给出一个最长的操作序列，先输出序列长度，然后按照顺序给出每次反转了哪个节点的颜色。

## 思路

## 实现

void get_sum(int p) {
    int num = 1;
    for (auto it : tr[p].child) {
        get_sum(it);
        num *= tr[it].sum;
    }
    tr[p].sum = num + 1;
}

Gym102896 C - Color the Tree

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Kattis Message （状态机模型 + 矩阵快速幂）

数论进阶——莫比乌斯反演

Codeforces Round #703 (Div. 2)

SDUT 2021 Winter Individual Contest - E

Kattis Fruit Slicer （计算几何 + 扫描线）

Gym 101147 A-The game of Osho

线性DP入门

Codeforces Round #703 (Div. 2)

Ubuntu24.04 配置虚空终端

Kattis Message （状态机模型 + 矩阵快速幂）

Gym102896 C - Color the Tree

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

Gym102896 C - Color the Tree

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款