#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
using namespace std ;
const int maxn = 1e6 + 10 , inf= 2e9 , mod = 1e9 + 7 , sq = 360 ,MX = 20000 ;
int dp[maxn][2] , mark[maxn];
vector <int> G[maxn] ;
void dfs(int v, int p =0 ){
dp[v][0] = dp[v][1]= 0;
if(mark[v]==1)dp[v][1] = inf ;
if(mark[v]==2)dp[v][0] = inf ;
for(int u : G[v]){
if(u == p)continue ;
dfs(u , v);
dp[v][0]= dp[v][0] + min(dp[u][1] + 1 , dp[u][0]) ;
dp[v][1]= dp[v][1] + min(dp[u][0] + 1 , dp[u][1]) ;
}
}
void initialize(int N , vector <int> a , vector <int> b){
rep(i , 0 , N-2){
G[a[i]+1].pb(b[i]+1) ;
G[b[i]+1].pb(a[i]+1) ;
}
}
int cat(int v){
mark[v]=1;
dfs(1);
return min(dp[1][0] , dp[1][1]) ;
}
int dog(int v){
mark[v]=2;
dfs(1) ;
return min(dp[1][0] , dp[1][1]) ;
}
int neighbor(int v){
mark[v] = 0 ;
dfs(1) ;
return min(dp[1][0] , dp[1][1]) ;
}
/*
signed main(){
int n ;
cin >> n ;
rep(i , 1, n-1){
int v,u;
cin >> v >> u ;
G[v].pb(u);
G[u].pb(v) ;
}
int t ;
cin >> t;
while(t--){
int x , v;
cin >> x >> v ;
if(x==1){
cout << dog(v) << "\n" ;
}else {
cout << cat(v) << "\n" ;
}
}
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
27228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
