#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)
const int N = 20;
int n;
vector<int> adj[N];
string s;
int par[N];
bool on[N];
int calc;
int cn[N];
int cnt(int node) {
int sum = 0;
if (on[node]) sum++;
for (int x : adj[node]) {
if (x == par[node]) continue;
par[x] = node;
sum += cnt(x);
}
cn[node] = sum;
return sum;
}
int dfs(int node, bool o) {
int has = 0;
bool no = o;
int t = 0;
for (int x : adj[node]) {
if (x == par[node]) continue;
t += min(1, cn[x]);
}
if (t >= 2 or on[node]) no = 1;
for (int x : adj[node]) {
if (x == par[node]) continue;
has += min(1, dfs(x, no));
}
if (o) has++;
if (on[node] and has <= 1) {
calc++;
} else if (has >= 2 and s[node - 1] == '1') {
calc--;
}
if (o) has--;
return min(has + on[node], 1);
}
int main() {
FIO;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
cin >> s;
int ans = 0;
for (int i = 0; i < (1 << n); i++) {
calc = 0;
for (int j = 0; j < n; j++) {
if (((1 << j) & i) and s[j] == '1') {
on[j + 1] = 1;
} else {
on[j + 1] = 0;
}
}
cnt(1);
dfs(1, 0);
ans = max(ans, calc);
}
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |