#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3HspL4A ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vec(int);
void print(){cout<<"\n";}
template<class T,class...E>
void print(const T&v,const E&...u){cout<<v<<' ',print(u...);}
// e
const int inf=1e9+11;
const int nax=100000;
int n,root,ru,usd[nax+11];
vi adj[nax+11];
void get_root(int v,int par){
if(root!=-1) return;
usd[v]=1;
for(auto u:adj[v]){
if(u==par) continue;
if(usd[u]){
root=v;
ru=u;
return;
}
get_root(u,v);
}
}
int xru,yru,dp[nax+11][2][2];
void affine(int v,int par){
rep(t,2)rep(t1,2) dp[v][t][t1]=inf;
if(xru){
if(yru) dp[v][1][1]=1;
dp[v][0][1]=0;
for(auto u:adj[v]){
if(u==par) continue;
if(u!=ru){
if(yru) dp[v][1][1]+=dp[u][0][0];
dp[v][0][1]+=dp[u][0][1];
}else{
if(yru) dp[v][1][1]+=dp[u][1][0];
dp[v][0][1]+=dp[u][1][yru];
}
}
}else{
dp[v][0][0]=0;
if(yru) dp[v][1][0]=1;
for(auto u:adj[v]){
if(u==par) continue;
if(u!=ru){
dp[v][0][0]+=dp[u][0][1];
if(yru) dp[v][1][0]+=dp[u][0][0];
}else{
dp[v][0][0]+=dp[u][0][yru];
if(yru) dp[v][1][0]+=dp[u][0][0];
}
}
for(auto u:adj[v]){
if(u==par or u==ru) continue;
dp[v][0][1]=min(dp[v][0][1],dp[v][0][0]-dp[u][0][1]+dp[u][1][1]);
if(yru) dp[v][1][1]=min(dp[v][1][1],dp[v][1][0]-dp[u][0][0]+dp[u][1][0]);
}
}
}
void quq(int v,int par){
dp[v][0][0]=0;
dp[v][1][0]=1;
bool pok=0;
for(auto u:adj[v]){
if(u==par) continue;
pok=pok or (u==ru);
quq(u,v);
dp[v][0][0]+=dp[u][0][1];
dp[v][1][0]+=dp[u][0][0];
}
dp[v][0][1]=dp[v][1][1]=inf;
for(auto u:adj[v]){
if(u==par) continue;
dp[v][0][1]=min(dp[v][0][1],dp[v][0][0]-dp[u][0][1]+dp[u][1][1]);
dp[v][1][1]=min(dp[v][1][1],dp[v][1][0]-dp[u][0][0]+dp[u][1][0]);
}
if(pok){
affine(v,par);
}
}
signed main(){
_3HspL4A;
cin>>n;
rep(i,n){
int u,v;
cin>>u>>v;
u-=1,v-=1;
adj[u].pb(v);
adj[v].pb(u);
}
root=-1;
get_root(0,-1);
{
rep(i,sz(adj[root])){
if(adj[root][i]==ru){
adj[root].erase(adj[root].begin()+i);
break;
}
}
rep(i,sz(adj[ru])){
if(adj[ru][i]==root){
adj[ru].erase(adj[ru].begin()+i);
break;
}
}
}
int ans=inf;
rep(t,2){
rep(t1,2){
yru=!t,xru=!t1;
rep(i,n){
dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=inf;
}
quq(root,-1);
ans=min(ans,dp[root][t][t1]);
}
}
print(ans>=inf?-1:ans);
//
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2588 KB |
Output is correct |
5 |
Correct |
164 ms |
19084 KB |
Output is correct |
6 |
Correct |
143 ms |
19060 KB |
Output is correct |
7 |
Correct |
121 ms |
19020 KB |
Output is correct |
8 |
Correct |
126 ms |
19084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
1 ms |
2644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
2 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2644 KB |
Output is correct |
5 |
Correct |
1 ms |
2644 KB |
Output is correct |
6 |
Correct |
2 ms |
2644 KB |
Output is correct |
7 |
Correct |
2 ms |
2644 KB |
Output is correct |
8 |
Correct |
1 ms |
2644 KB |
Output is correct |
9 |
Correct |
1 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
1 ms |
2644 KB |
Output is correct |
13 |
Correct |
2 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2772 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
2 ms |
2644 KB |
Output is correct |
17 |
Correct |
2 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
2 ms |
2644 KB |
Output is correct |
20 |
Correct |
2 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2644 KB |
Output is correct |
22 |
Correct |
3 ms |
2644 KB |
Output is correct |
23 |
Correct |
3 ms |
2772 KB |
Output is correct |
24 |
Correct |
2 ms |
2772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2644 KB |
Output is correct |
2 |
Correct |
2 ms |
2644 KB |
Output is correct |
3 |
Correct |
1 ms |
2644 KB |
Output is correct |
4 |
Correct |
2 ms |
2588 KB |
Output is correct |
5 |
Correct |
164 ms |
19084 KB |
Output is correct |
6 |
Correct |
143 ms |
19060 KB |
Output is correct |
7 |
Correct |
121 ms |
19020 KB |
Output is correct |
8 |
Correct |
126 ms |
19084 KB |
Output is correct |
9 |
Correct |
3 ms |
2644 KB |
Output is correct |
10 |
Correct |
2 ms |
2644 KB |
Output is correct |
11 |
Correct |
2 ms |
2644 KB |
Output is correct |
12 |
Correct |
2 ms |
2644 KB |
Output is correct |
13 |
Correct |
1 ms |
2644 KB |
Output is correct |
14 |
Correct |
2 ms |
2644 KB |
Output is correct |
15 |
Correct |
2 ms |
2644 KB |
Output is correct |
16 |
Correct |
1 ms |
2644 KB |
Output is correct |
17 |
Correct |
1 ms |
2644 KB |
Output is correct |
18 |
Correct |
2 ms |
2644 KB |
Output is correct |
19 |
Correct |
2 ms |
2644 KB |
Output is correct |
20 |
Correct |
1 ms |
2644 KB |
Output is correct |
21 |
Correct |
2 ms |
2644 KB |
Output is correct |
22 |
Correct |
2 ms |
2772 KB |
Output is correct |
23 |
Correct |
2 ms |
2644 KB |
Output is correct |
24 |
Correct |
2 ms |
2644 KB |
Output is correct |
25 |
Correct |
2 ms |
2644 KB |
Output is correct |
26 |
Correct |
2 ms |
2644 KB |
Output is correct |
27 |
Correct |
2 ms |
2644 KB |
Output is correct |
28 |
Correct |
2 ms |
2644 KB |
Output is correct |
29 |
Correct |
2 ms |
2644 KB |
Output is correct |
30 |
Correct |
3 ms |
2644 KB |
Output is correct |
31 |
Correct |
3 ms |
2772 KB |
Output is correct |
32 |
Correct |
2 ms |
2772 KB |
Output is correct |
33 |
Correct |
64 ms |
9428 KB |
Output is correct |
34 |
Correct |
64 ms |
9416 KB |
Output is correct |
35 |
Correct |
71 ms |
9404 KB |
Output is correct |
36 |
Correct |
89 ms |
9360 KB |
Output is correct |
37 |
Correct |
13 ms |
4360 KB |
Output is correct |
38 |
Correct |
80 ms |
9392 KB |
Output is correct |
39 |
Correct |
5 ms |
3156 KB |
Output is correct |
40 |
Correct |
76 ms |
9316 KB |
Output is correct |
41 |
Correct |
53 ms |
10492 KB |
Output is correct |
42 |
Correct |
68 ms |
10444 KB |
Output is correct |
43 |
Correct |
199 ms |
18960 KB |
Output is correct |
44 |
Correct |
86 ms |
14668 KB |
Output is correct |