| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 429185 | Ozy | Star Trek (CEOI20_startrek) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (lli i = (a); i <= (b); i++)
#define repa(i,a,b) for (lli i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define MAX 100000
#define mod 1000000007
lli n,d,a,b,g,p;
lli arr[3][MAX+2];
vector<lli> hijos[MAX+2];
lli ini(lli pos, lli padre) {
lli res = 1;
for (auto h : hijos[pos]) {
if (h == padre) continue;
a = ini(h,pos);
arr[a][pos]++;
res *= a;
}
if (res == 0) {arr[2][pos] = 1; return 1;}
else {arr[2][pos] = 0; return 0;}
}
void DFS(lli pos, lli padre,lli val) {
lli act;
arr[val][pos]++;
if (arr[0][pos] > 0) g++;
else p++;
for (auto h : hijos[pos]){
if (h == padre) continue;
arr[arr[2][h]][pos]--;
if (arr[0][pos] > 0) act = 1;
else act = 0;
arr[arr[2][h]][pos]++;
DFS(h,pos,act);
}
arr[val][pos]--;
}
void resuelve()
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> d;
rep(i,1,n-1) {
cin >> a >> b;
hijos[a].push_back(b);
hijos[b].push_back(a);
}
a = ini(1,0);
DFS(1,0,1);
total = 0;
resuelve(1,0);
cout << total;
}