## [P6150 [USACO20FEB] Clock Tree S](https://www.luogu.com.cn/problem/P6150)

#### 前置知识：图上dfs

## 思路

### $PART$ $1$

这道题给出我们的是一个 $n$ 个房间， $n-1$ 条走廊，其实就是 $n$ 个点， $m$ 条边。每一个房间都可以走到另外的房间，说明它是连通的，那么 $n$ 个点 $n-1$ 条边连通的一个图，那这道题给我们的就是一棵树。

### $PART$ $2$

他既然要求那一个节点是可以当作起点，那就可以把它当作这棵树的根来看。所以我们可以枚举每一个点，看看这个点是不是可以把所以的房间都变成 $12$ ，最后再统计答案就可以了。

### $PART$ $3$

假设现在从点 $u$ 到点 $v$ ，要把这个点 $v$ 给改成 $12$ ,既然我们可以发现可以从 $u$ 到 $v$ ，再从点 $v$ 到 $u$ 。那么最后总能把这个点 $v$ 调成 $12$ 。那调完 $v$ 以后呢？ $u$ 也总得改值吧。如果是这样来把孩子的的值调整为 $12$ ，那么 $u$ 和 $v$ 一直的差也是不变的，所以 $u$ 就等于 $(u+(12-v)$ 。但是在计算 $u$ 到 $v$ 的话，必须得先把 $v$ 能到的点先给改成 $12$ ，但是不能遍历到 $u$ 。

### $PART$ $4$

最后，我们就可以看一下当做起点的值是不是变成了 $12$ 。其实变成 $1$ 也可以。我们可以在最后的那个点再蹦回来的时候，就截至，就不让最后那个点在返回来让起点 $+1$ 。也就是把起点变回了 $12$ 。

## 代码

```cpp
//
// Created by 55062 on 2023/11/18.
//
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n, a[2510], u, v, t[2510], ans;
vector<ll> adj[2510];

void dfs(ll x, ll fa) { // x 代表这个点， fa 就是它的父节点
    for (int i = 0; i < adj[x].size(); i++) {
        ll o = adj[x][i];
        if (o == fa) continue; //不能再遍历回去
        dfs(o, x);
        //前去遍历他的孩子，在计算
        t[x] = (t[x] + (12 - t[o])) % 12; //计算
        t[o] = 0; //可以不用，因为后面页也不遍历到这个点了
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; //初始值
        a[i] %= 12;
    }
    for (int i = 1; i < n; i++) {
        cin >> u >> v;
        adj[u].push_back(v); //建边
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) t[j] = a[j]; //重新赋值
        dfs(i * 1ll, 0ll); //我的是 long long 类型的
        if (t[i] == 1 || t[i] == 0) ans++; //如过可以，那么答案+1
    }
    cout << ans;
    return 0;
}
```

原因是 LaTeX 公式/英文与汉字之间少空格； 。