Submission #286729

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define repf(i, f, l) for(int i = f; i < (int)l; ++i)

#ifdef ONLINE_JUDGE
#define DEBUG false
#else
#define DEBUG true
#endif

#define pb emplace_back
#define lb lower_bound
#define ul unsigned long
#define ull unsigned long long
#define ll long long
#define INF 1000000007
#define MOD 1000000007
#define fs first
#define sd second

#define ALL(c) (c).begin(),(c).end()

#define DBG0(x)    {if(DEBUG){ cout << #x << ": " << x << "\t"; }}
#define DBG(x)     {if(DEBUG){DBG0(x); cout << endl;}}
#define DBG2(x, y) {if(DEBUG){DBG0(x); DBG(y);}}
#define DBG3(x, y, z) {if(DEBUG){DBG0(x); DBG2(y, z);}}
#define DBG4(w, x, y, z) {if(DEBUG){DBG0(w); DBG3(x, y, z);}}

template <class T>
ostream& operator<<(ostream& os, vector<T> xs){ for(T x: xs) os << x << ' '; return os; }
template <class S, class T>
ostream& operator<<(ostream& os, pair<S,T> st){ os << "(" << st.first << "," << st.second <<")"; return os; }

typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<ul> vul;
typedef vector<ull> vull;
typedef vector<bool> vbl;
typedef pair<int, int> pii;

int main(void){
    int n, x;
    cin >> n >> x;
    vector<int> h(n);
    rep(i, n) cin >> h[i];
    vector<vector<int>> edge(n, vector<int>(n, 0));
    rep(i, n - 1){
        int a, b;
        cin >> a >> b;
        a--; b--;
        edge[a][b] = 1;
        edge[b][a] = 1;
    }
    vector<int> deg(n, 0);
    rep(i, n) rep(j, n) if(edge[i][j]) deg[i]++;

    for(bool flg = true; flg; ){
        flg = false;
        rep(i, n){
            if(deg[i] == 1 && !h[i]){
                flg++;
                deg[i] = 0;
                rep(j, n){
                    if(edge[i][j]){
                        edge[i][j] = 0;
                        edge[j][i] = 0;
                        deg[j]--;
                    }
                }
            }
        }
    }
    int ans = 0;
    rep(i, n) rep(j, n) ans += edge[i][j];
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result