boj/18785.cpp at main · joonghak/boj · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define ll long long
using namespace std;

const ll INF = 1e9 + 7;
const ll DIV = 987654321;

int n;
int arr[3000];

int val[3000];

vector<int> adj[3000];

int get(int cur, int prv){

    int sm = 0;
    for(int nxt : adj[cur]){
        if(nxt == prv) continue;
        sm += -(get(nxt, cur) + 1) + 1;
    }
    sm = (sm% 12 + 12) % 12;
    return val[cur] = (sm+ arr[cur]) % 12;
}

bool f;

void go(int cur, int prv, int k){
    vector<int> v;
    int sm = 0;
    for(int nxt : adj[cur]){
        if(nxt == prv) continue;
        int t = -(val[nxt] + 1) % 12 + 1;
        v.push_back(t);
        sm += t;
    }
    sm += k;

    sm = (sm% 12 + 12) % 12;

    if(sm == 0) f = 1;

    for(int nxt : adj[cur]){
        if(nxt == prv) continue;
        int t = -(val[nxt] + 1) % 12 + 1;
        go(nxt, cur, arr[nxt] + 1 - sm + t);
    }
}

int main()
{
    fastio;
    cin >> n;
    for(int i = 1;i<=n;i++) cin >> arr[i];
    for(int i = 0 ;i < n - 1;i++) {
        int a, b;
        cin >> a>> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int ans = 0;
    for(int i = 1;i<=n;i++){
        get(i, i);
        f = 0;
        go(i ,i, arr[i]);
        if(f) ans++;
    }

    cout << ans << "\n";
    return 0;
}