Submission #2480847


Source Code Expand

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int MAX = 110;
int h[MAX];
int cost[MAX];
vector<int> G[MAX];

bool dfs(int from, int now){
    if(G[now].size() == 1 && h[now] == 0) return false;
    bool flag = false;
    for(auto next : G[now]){
        if(next == from) continue;
        if(dfs(now, next)) flag = true;
    }
    if(flag || h[now] == 1) cost[from] += cost[now] + 2;
    else return false;
    return true;
}

int main(){
    int N,root; cin >> N >> root;
    root--;
    for(int i=0;i<N;i++) cin >> h[i];
    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);
    }
    for(auto v : G[root]) dfs(root, v);
    cout << cost[root] << endl;
    return 0;
}

Submission Info

Submission Time
Task B - ツリーグラフ
User okesaku
Language C++14 (GCC 5.4.1)
Score 100
Code Size 822 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