Submission #287600

---

Source Code Expand

#include <iostream>
#include <stdio.h>
#include <istream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cstring>


using namespace std;

typedef long long int ll;

const int MAX_N = 100;
int N;

vector<int> G[MAX_N];
bool used[MAX_N];
bool h[MAX_N];
bool transh[MAX_N];


// contain?
bool dfs(int v) {
    used[v] = true;
    
    bool ans = h[v];
    for (int i = 0; i < G[v].size(); i++) {
        if (!used[G[v][i]]) {
            ans |= dfs(G[v][i]);
        }
    }
    transh[v] = ans;
    return ans;
}

int dfs2(int v) {
    used[v] = true;
    
    int ans = 0;
    for (int i = 0; i < G[v].size(); i++) {
        int to = G[v][i];
        if (!used[to] && transh[to]) {
            ans += 1 + dfs2(to);
        }
    }

    return ans;
}


int main(int argc, const char * argv[])
{
    int _x;
    cin >> N >> _x;
    const int x = _x - 1;
    
    
    int hcount = 0;
    for (int i = 0; i < N; i++) {
        int b;
        cin >> b;
        h[i] = (b == 1);
        if (b == 1) { hcount++; };
    }
    
    for (int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    
    memset(used, 0, sizeof(used));
    dfs(x);
    
//    for (int i = 0; i < N; i++) {
//        cout << transh[i] << endl;
//    }
//    cout << endl;
    
    memset(used, 0, sizeof(used));
    int ret = dfs2(x);
    
    cout << ret * 2 << endl;
}

Submission Info

Judge Result