#include <bits/stdc++.h>
using namespace std;
#define lg long long
const lg N = 2e5+5;
vector<lg> adj[N], adj2[N];
lg dp[N][4], par[N], vis[N], tmp;
lg get(lg src)
{
if(par[src] == src) return src;
return par[src] = get(par[src]);
}
lg dfs(lg src, lg b, lg par = -1)
{
b &= 3;
auto&ret = dp[src][b];
if(~ret) return ret;
ret = 1e18;
lg sum = 0;
if(adj[src].empty()) ret = 0;
for(auto it : adj[src])
{
if(it == par) continue;
sum += dfs(it, (b << 1), src);
}
if(b&2)
{
// cout << src << ' ' << b << '\n';
// cout << sum << '\n';
ret = sum;
return ret;
}
for(auto it : adj[src])
{
if(it == par) continue;
ret = min(ret, dfs(it, (b << 1)|1, src)-dfs(it, (b << 1), src)+sum+1);
}
// cout << src << ' ' << b << '\n';
// cout << ret << '\n';
return ret;
}
lg odd_cycle(lg src, lg par = -1)
{
vis[src] = ++tmp;
for(auto it : adj2[src])
{
if(it == par) continue;
if(vis[it])
{
return (vis[src]-vis[it]-1)%2;
}
if(odd_cycle(it, src)) return true;
}
return 0;
}
int main()
{
lg n;
cin >> n;
for(int i = 1; i <= n; i++) par[i] = i;
for(int i = 0; i < n; i++)
{
lg u, v;
cin >> u >> v;
int a = get(u), b = get(v);
adj2[u].push_back(v);
adj2[v].push_back(u);
if(a == b) continue;
par[a] = b;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(dp, -1, sizeof(dp));
dfs(1, 0);
dfs(1, 1);
cout << min(dp[1][0], dp[1][1]+1) << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
19036 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
