#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define T int t;cin >> t;while(t--)
#define int long long
#define F first
#define S second
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e6;
int n, depth[N], color[N], v1, v2;
vector<int> adj[N], vec;
bool cmp(int &x, int &y) {
if (depth[x] == depth[y]) return x < y;
return depth[x] < depth[y];
}
void dfs(int node, int dep) {
vec.push_back(node);
depth[node] = dep;
for(auto x: adj[node]) {
if (depth[x] == 0)
dfs(x, dep + 1);
}
}
stack<int> s;
bool solve() {
while (vec.size()) {
int dep = depth[vec.back()];
while (vec.size() && depth[vec.back()] == dep)
s.push(vec.back()), vec.pop_back();
while(s.size()) {
int u = s.top();
s.pop();
int cnt[4] = {0, 0, 0, 0};
for(auto x: adj[u]) {
if (depth[x] > depth[u])
cnt[color[x]]++;
}
if ((cnt[0] || cnt[2]) && (cnt[1] || cnt[3])) return 0;
if (cnt[0] > 0) {
if (cnt[2] == 0) {
color[u] = 2;
for(auto x: adj[u])
if (depth[x] > depth[u] && color[x] == 0) color[x] = 1;
}
else if (cnt[2] == 1) {
color[u] = 3;
for(auto x: adj[u])
if (color[x] == 3) color[x] = 3;
}
else return 0;
}
else if (cnt[2] > 0) {
if (cnt[2] > 1) return 0;
else {
color[u] = 3;
for(auto x: adj[u])
if (color[x] == 2) color[x] = 3;
}
}
else if (cnt[3] > 0) {
if (cnt[3] > 1) return 0;
color[u] = 1;
}
}
}
if (color[v1] == 0) {
if (color[v2] != 3) return 0;
color[v1] = 1;
}
else if (color[v1] == 1) {
if (color[v2] != 1) return 0;
}
else if (color[v1] == 2) {
if (color[v1] != 2) return 0;
color[v1] = color[v2] = 3;
}
else {
if (color[v2] != 0) return 0;
}
bool ok = 1;
for(int i = 1; i <= n; i++) ok &= (color[i] % 2);
return ok;
}
main() {
cin >> n;
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cin >> v1 >> v2;
int ans = 1e18;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) color[j] = depth[j] = 0;
vec.clear();
dfs(i, 1);
sort(begin(vec), end(vec), cmp);
if (solve()) {
int cnt = 0;
for(int j = 1; j <= n; j++) cnt += color[j] == 3;
ans = min(ans, cnt);
}
}
if (ans == 1e18) ans = -1;
cout << ans;
}
Compilation message
Main.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
88 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23736 KB |
Output is correct |
| 3 |
Correct |
11 ms |
23772 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
23740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
12 ms |
23736 KB |
Output is correct |
| 3 |
Correct |
11 ms |
23772 KB |
Output is correct |
| 4 |
Incorrect |
12 ms |
23764 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
