Also available: UVALive 6957, Kattis hyacinth, UESTC 1119

题意

在一个网络中给出 n 个节点，每个节点最多可以有两种频率，又给出 n-1 条边（题目保证形成树），要求每条边上的两个节点必须至少有一种频率相同，如果一种频率两个相连的节点所使用，那么这种频率就算做已使用的频率。要求使已使用频率的种数尽可能多，输出每个节点的频率。

解题思路

DFS 一下，每个节点的第一种频率继承父节点的频率。为了使已用频率种数尽可能多，需要尽量分配新的频率，所以要给当前节点的第二种频率分配一种新的频率，并且优先给孩子节点分配新的频率。所以我们可以给第一个分配第二种频率，其他孩子节点分配第一种频率（也可以第二种/第一种交替分配）。

参考代码

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 10001;

vector<int> edges[MAXN];
int freq[MAXN][2], idx;

void DFS(int u, int p, int f) {
    freq[u][0] = f;
    freq[u][1] = idx++; // 第二种频率设为新频率
    int cnt = 0;
    for(int i=0; i<edges[u].size(); ++i) {
        int v = edges[u][i];
        if(v != p) {
            if(cnt == 0) DFS(v, u, freq[u][1]); // 优先分配新频率
            else DFS(v, u, freq[u][0]);
            cnt++;
        }
    }
}

int main(int argc, char const *argv[]) {
    int n, u, v;
    while(~ scanf("%d", &n)) {
        for(int i=1; i<=n; ++i) {
            edges[i].clear();
        }
        for(int i=0; i<n-1; ++i) {
            scanf("%d %d", &u, &v);
            edges[u].push_back(v);
            edges[v].push_back(u);
        }
        if(n == 2) printf("0 1\n1 0\n");
        else {
            idx = 1;
            DFS(1, -1, 0);
            for(int i=1; i<=n; ++i) {
                printf("%d %d\n", freq[i][0], freq[i][1]);
            }
        }
    }
    
    return 0;
}