Submission #1371148


Source Code Expand

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define REP(i,n) FOR(i,0,n)

//#define int long long
typedef long long ll;
const ll INF = 1e18;
using namespace std;

int n, x;
int h[110];
int a, b;
vector<int> G[110];
bool visited[110];

pair<bool, int> dfs(int v)
{
    visited[v] = true;

    bool exist = (h[v] == 1);
    int cost = 0;

    REP(i,G[v].size()) {
        int nv = G[v][i];
        if (visited[nv]) continue;
        pair<bool, int> ret = dfs(nv);
        exist |= ret.first;
        if (ret.first) {
            cost += 2 + ret.second;
        }
    }

    return make_pair(exist, cost);
}

signed main()
{
    cin >> n >> x;
    x--;
    REP(i,n) cin >> h[i];
    REP(i,n-1) {
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    cout << dfs(x).second << endl;
}

Submission Info

Submission Time
Task B - ツリーグラフ
User hiyokko2
Language C++14 (GCC 5.4.1)
Score 100
Code Size 905 Byte
Status AC
Exec Time 1 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 2
AC × 20
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask1_line01.txt, subtask1_line02.txt, subtask1_line03.txt, subtask1_line04.txt, subtask1_line05.txt, subtask1_line06.txt, subtask1_random01.txt, subtask1_random02.txt, subtask1_random03.txt, subtask1_random04.txt, subtask1_random05.txt, subtask1_random06.txt, subtask1_random07.txt, subtask1_random08.txt, subtask1_special01.txt, subtask1_special02.txt, subtask1_special03.txt, subtask1_special04.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 1 ms 256 KB
subtask0_sample_02.txt AC 1 ms 256 KB
subtask1_line01.txt AC 1 ms 256 KB
subtask1_line02.txt AC 1 ms 256 KB
subtask1_line03.txt AC 1 ms 256 KB
subtask1_line04.txt AC 1 ms 256 KB
subtask1_line05.txt AC 1 ms 256 KB
subtask1_line06.txt AC 1 ms 256 KB
subtask1_random01.txt AC 1 ms 256 KB
subtask1_random02.txt AC 1 ms 256 KB
subtask1_random03.txt AC 1 ms 256 KB
subtask1_random04.txt AC 1 ms 256 KB
subtask1_random05.txt AC 1 ms 256 KB
subtask1_random06.txt AC 1 ms 256 KB
subtask1_random07.txt AC 1 ms 256 KB
subtask1_random08.txt AC 1 ms 256 KB
subtask1_special01.txt AC 1 ms 256 KB
subtask1_special02.txt AC 1 ms 256 KB
subtask1_special03.txt AC 1 ms 256 KB
subtask1_special04.txt AC 1 ms 256 KB