Submission #1686692

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int g[110][110];
vector<int> vec[100];
int n, x;
int h[110];
int tmp;
int used[110];

void bt(int nd) {
    used[nd] = 1;
    imfor(i, n) {
        if (g[nd][i] == 1 && used[i] == 0) {
            vec[nd].push_back(i);
            bt(i);
        }
    }
}

int check(int nd) {
    if (h[nd] == 1) {
        return 1;
    }
    for (auto x : vec[nd]) {
        if (h[x] == 1) {
            return 1;
        }
        if (check(x) == 1) {
            return 1;
        }
    }
    return 0;
}

void cnt(int rt) {
    for (auto x : vec[rt]) {
        if (check(x) == 1) {
            tmp += 2;
            cnt(x);
        }
    }
}

int main() {
    cin >> n >> x;
    imfor(i, n) {
        int hs;
        cin >> hs;
        h[i] = hs;
    }
    imfor(i, n) {
        imfor(j, n) {
            g[i][j] = 0;
        }
    }
    imfor(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        g[a][b] = 1;
        g[b][a] = 1;
    }
    int ans = 99999999;
    imfor(i, n) {
        imfor(j, n) {
            vec[j].clear();
        }
        imfor(j, n) {
            used[j] = 0;
        }
        bt(i);
        tmp = 0;
        cnt(i);
        ans = min(ans, tmp);
    }
    cout << ans << endl;
}

Submission Info

Judge Result