[Easy-Medium] CF1879E Interactive Game with Coloring

简要题意

这是一道交互题。

给定一个 $n$ 个点的树，根节点为 $1$，你需要给出一个 $k$，然后用 $k$ 种颜色给每条边染色。

接下来，交互库会选择一个非根的点 $u$，然后进行若干轮游戏。

每轮游戏交互库会先给出一个 $o$，若 $o=1$ 表示 $u=1$，游戏结束，否则会给出一个长度为 $k$ 的序列 $a$，表示一端点为 $u$ 的所有边中，颜色为 $i$ 的边数为 $a_i$。然后你需要输出一个颜色，然后交互库会选择一条为你给出的颜色的边，然后将 $u$ 设定为另一个端点。

你需要在最少的轮数结束游戏，同时要求 $k$ 最小。注意操作库是自适应的。

$1\leq n\leq 100$。

思路

令 $d_i$ 表示点 $i$ 的深度，$f_i$ 表示 $i$ 的父节点，$c_i$ 表示边 $(f_i,i)$ 的颜色。

Part 1

首先注意到题意相当于给树边染色，使得 $(f_i,i)$ 的颜色与其他端点为 $i$ 的边不同（如果点 $i$ 度数为 $2$，我们还要要求可以确定 $(f_i,i)$ 的颜色）。

最优的 $k$ 最大值为 $3$。

证明：取 $c_i=d_i\bmod 3 + 1$，那么可以通过点 $i$ 哪些颜色存在边，简单分类讨论推出哪个点是父节点。

但是并不满足最优的 $k=3$，样例就给出了两组例子。不过好在现在只需要讨论 $k=1,2,3$ 三种情况了。

对于 $k=1$，是简单的，一定是菊花图，否则一定无法确定。最复杂的情况便是 $k=2$。

Part 2

现在我们需要了解，为什么 $k$ 不总等于 $2$，这是因为树上会存在度数为 $2$ 的点 $i$，这个时候确定 $c_i$ 比较困难。因此，如果存在这样的 $i$，必须保证所有 $(f_i,i)$ 的颜色全部相同（要不然根据有限的信息无法推出来，如果推出来总能被交互库 hack）。

由于颜色是对称的，于是可以将所有度数为 $2$ 的点 $i$ 的 $c_i$ 钦定一种颜色，为了方便，不妨将颜色附着在深度较大的点上，跑一个类似二分图染色的过程即可。注意 $1$ 的出边颜色允许不同（要不然会 WA on #4）。

如果存在一组合法的方案，就可以用 $k=2$，否则就按照 $k=3$ 的方法跑即可。时间复杂度 $O(n)$。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n, fa[N], dep[N];
vector<int> g[N];
int col[N];

void dfs1(int u){
    for(int v : g[u]) dep[v] = dep[u] + 1, dfs1(v);
}

bool dfs2(int u, int color){
    if(col[u] && col[u] != color) return false;
    col[u] = color;
    for(int v : g[u]){
        if(!dfs2(v, 3 - color)) return false;
    }
    return true;
}

void clear(int u){
    if(g[u].size() != 1) col[u] = 0;
    for(int v : g[u]) clear(v);
}

signed main(){
    cin >> n;
    for(int i=2;i<=n;i++) cin >> fa[i], g[fa[i]].push_back(i);
    dfs1(1);
    for(int i=1;i<=n;i++){
        if(g[i].size() == 1) col[i] = 1;
    }
    bool flag = 1;
    for(int i : g[1]){
        if(!dfs2(i, 1)){
            clear(i);
            if(!dfs2(i, 2)){
                flag = 0;
                break;
            }
        }
    }
    if(count(fa + 2, fa + n + 1, 1) == n - 1){
        cout << "1" << endl;
        for(int i=2;i<=n;i++) cout << 1 << ' ';
        cout << endl;
        cout.flush();
        while(true){
            int op; cin >> op;
            assert(op != -1);
            if(op) break;
            int a; cin >> a;
            cout << 1 << endl;
            cout.flush();
        }
    }
    else if(flag){
        cout << "2" << endl;
        for(int i=2;i<=n;i++) cout << col[i] << ' ';
        cout << endl;
        cout.flush();
        while(true){
            int op; cin >> op;
            assert(op != -1);
            if(op) break;
            int a, b; cin >> a >> b;
            if(a == 1 && b != 1) cout << 1 << endl;
            else if(a != 1 && b == 1) cout << 2 << endl;
            else cout << 1 << endl;
            cout.flush();
        }
    }
    else{
        cout << "3" << endl;
        for(int i=2;i<=n;i++) cout << (dep[i] % 3 + 1) << ' ';
        cout << endl;
        cout.flush();
        while(true){
            int op; cin >> op;
            assert(op != -1);
            if(op) break;
            int a, b, c; cin >> a >> b >> c;
            if(!a && !b) cout << 3 << endl;
            else if(!b && !c) cout << 1 << endl;
            else if(!a && !c) cout << 2 << endl;
            else if(!a) cout << 2 << endl;
            else if(!b) cout << 3 << endl;
            else cout << 1 << endl;
            cout.flush();
        }
    }
    return 0;
}

// Written by xiezheyuan