P6150 [USACO20FEB]Clock Tree S题解

· · 题解

因为题目求起点有多少个，那么我们依次枚举每个点作为起点，把它当做树根，从它出发往孩子走，看看能不能做到。

每当Farmer John沿着一条线在树上走的时候，遇到的每个点时间都往前加1。考虑从树上某个结点u走到它的孩子v，那么u和v上的时间都往前加1了。也就是说要改就父子一起改，父子之间的差是不变的。既然题目中是验证是否能完成，我们不妨贪心地看，每次不停地从父子之间来回走，直到把孩子改成12，这时候根据父子差固定，我们就能知道u现在是多少。然后再去搞下一个孩子，再确定u的值。直到把所有孩子都改好，此时u固定到了某个数。回到上一层，再由父亲把u改成12

那么这么一轮下来，最后除了根，其他点都是12了。那么根如果正好是12，说明是可以的。如果根不是12呢？其实根是1也行，因为这样就最后的时候从根的最后一个孩子停下，不走回来。这时候根和最后一个孩子的时间会差一个。除了这两种情况，其他都不行。

这样枚举每个点做根，每次根确定以后，一遍dfs，总的时间复杂度是O(n^2)，不超时。实际写的时候，用一个c数组表示每个点现在的时间，然后用0表示12，这样每次对12取模就行了，写起来比较方便。最终目标也是把所有点调成0.

代码如下：

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

using namespace std;
const int MAXN = 2505;
int n, c[MAXN], t[MAXN], ans;
vector<int> adj[MAXN];

void dfs(int u, int f) {
    for (int i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == f) continue;
        //先递归孩子，把孩子调到0
        dfs(v, u);
        //当前点和孩子的差不变，求出当前点的值
        t[u] = (t[u] - t[v] + 12) % 12;
    }
}

int main() {
//    freopen("clocktree.in","r",stdin);
//    freopen("clocktree.out","w",stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &c[i]);
        c[i] %= 12;
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i) {
        //先把c数组拷贝到t数组里面，去操作t数组。免得c被改掉了下次循环数不对了。
        memcpy(t, c, sizeof(t));
        dfs(i, 0);
        //最后根上剩下0或者1就是可以的
        if (t[i] == 0 || t[i] == 1) ans++;
    }
    cout << ans << endl;
    return 0;
}

后记，后来比赛完才想起来有个O(n)的二分染色算法，其他大佬写过题解了，我就不写了。