Submission #286590


Source Code Expand

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

vector<int> H;
vector<vector<int> > G;

int cnt(int now, int parent) {
  int res = 0;
  if (H[now]) res ++;
  for (int i=0; i<G[now].size(); i++) {
    int nxt = G[now][i];
    if (nxt == parent) continue;
    res += cnt(nxt, now);
  }
  return res;
}

int go(int now, int parent) {
  int res = 0;
  for (int i=0; i<G[now].size(); i++) {
    int nxt = G[now][i];
    if (nxt == parent) continue;
    if (!cnt(nxt, now)) continue;
    res += 2;
    res += go(nxt, now);
  }
  return res;
}

int main()
{
  int n, start;
  cin >> n >> start;
  start --;
  H.resize(n);
  G.resize(n);
  for (int i=0; i<n; i++) cin >> H[i];
  for (int i=0; i<n-1; i++) {
    int a, b;
    cin >> a >> b;
    G[a-1].push_back(b-1);
    G[b-1].push_back(a-1);
  }

  cout << go(start, -1) << endl;
}

Submission Info

Submission Time
Task B - ツリーグラフ
User ainu7
Language C++ (G++ 4.6.4)
Score 100
Code Size 1074 Byte
Status AC
Exec Time 24 ms
Memory 928 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 22 ms 800 KB
subtask0_sample_02.txt AC 22 ms 924 KB
subtask1_line01.txt AC 22 ms 920 KB
subtask1_line02.txt AC 23 ms 848 KB
subtask1_line03.txt AC 23 ms 800 KB
subtask1_line04.txt AC 22 ms 928 KB
subtask1_line05.txt AC 22 ms 788 KB
subtask1_line06.txt AC 21 ms 928 KB
subtask1_random01.txt AC 23 ms 676 KB
subtask1_random02.txt AC 22 ms 804 KB
subtask1_random03.txt AC 20 ms 928 KB
subtask1_random04.txt AC 22 ms 800 KB
subtask1_random05.txt AC 22 ms 800 KB
subtask1_random06.txt AC 22 ms 856 KB
subtask1_random07.txt AC 22 ms 800 KB
subtask1_random08.txt AC 24 ms 920 KB
subtask1_special01.txt AC 23 ms 792 KB
subtask1_special02.txt AC 23 ms 788 KB
subtask1_special03.txt AC 22 ms 920 KB
subtask1_special04.txt AC 22 ms 800 KB