#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
#include "catdog.h"
int x;
vector<int> adj[100001];
int dp[100001][2];
int it[100001];
int par[100001];
int ss[100001];
int st[100001];
int par3[100001];
int n;
vector<vector<vector<int>>> tree[100001];
vector<int> pre[100001];
void dfs(int no,int par2=-1){
ss[no]=1;
par[no]=par2;
vector<pair<int,int>> tt;
for(auto j:adj[no]){
if(j!=par2){
dfs(j,no);
tt.pb({ss[j],j});
ss[no]+=ss[j];
}
}
sort(tt.begin(),tt.end());
adj[no].clear();
while(tt.size()){
adj[no].pb(tt.back().b);
tt.pop_back();
}
}
int co=0;
void dfs2(int no,int par2=-1){
par3[no]=no;
st[no]=co;
co++;
if(par2!=-1){
if(st[no]==st[par2]+1){
par3[no]=par3[par2];
}
}
// ind[no]=pre[par3[no]].size();
pre[par3[no]].pb(no);
vector<int> kk;
kk.pb(0);
kk.pb(0);
vector<vector<int>> ll;
ll.pb(kk);
ll.pb(kk);
for(int i=0;i<4;i++){
tree[par3[no]].pb(ll);
}
for(auto j:adj[no]){
if(j!=par2){
dfs2(j,no);
}
}
}
void build(int ind,int no,int l,int r){
if(l==r){
tree[ind][no][0][0]=0;
tree[ind][no][1][1]=0;
tree[ind][no][1][0]=1e9;
tree[ind][no][0][1]=1e9;
}
else{
int mid=(l+r)/2;
build(ind,no*2+1,l,mid);
build(ind,no*2+2,mid+1,r);
}
}
void update(int ind,int no,int l,int r,int i,int j){
if(l==r){
tree[ind][no][0][0]=dp[j][0];
tree[ind][no][1][1]=dp[j][1];
if(it[j]==2){
tree[ind][no][0][0]=1e9;
}
if(it[j]==1){
tree[ind][no][1][1]=1e9;
}
// cout<<j<<","<<tree[ind][no][0][0]<<","<<tree[ind][no][1][1]<<endl;
tree[ind][no][1][0]=1e9;
tree[ind][no][0][1]=1e9;
}
else{
int mid=(l+r)/2;
if(i<=mid){
update(ind,no*2+1,l,mid,i,j);
}
else{
update(ind,no*2+2,mid+1,r,i,j);
}
tree[ind][no][0][0]=1e9;
tree[ind][no][1][1]=1e9;
tree[ind][no][1][0]=1e9;
tree[ind][no][0][1]=1e9;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
for(int l=0;l<2;l++){
for(int k=0;k<2;k++){
int x=1;
if(j==l){
x=0;
}
tree[ind][no][i][k]=min(tree[ind][no][i][k],tree[ind][no*2+1][i][j]+tree[ind][no*2+2][l][k]+x);
}
}
}
}
}
}
void initialize(int nn, std::vector<int> aa, std::vector<int> bb) {
n=nn;
for(int i=0;i<n-1;i++){
adj[aa[i]-1].pb(bb[i]-1);
adj[bb[i]-1].pb(aa[i]-1);
}
dfs(0);
dfs2(0);
for(int i=0;i<n;i++){
if(pre[i].size()){
build(i,0,0,pre[i].size()-1);
}
}
for(int i=0;i<n;i++){
it[i]=0;
dp[i][0]=0;
dp[i][1]=0;
}
}
void apply(int i){
//<int> xx;
int cur=i;
while(true){
cur=par3[cur];
if(cur==0){
break;
}
dp[par[cur]][0]-=min(min(tree[cur][0][0][0],tree[cur][0][0][1]),min(tree[cur][0][1][0],tree[cur][0][1][1])+1);
dp[par[cur]][1]-=min(min(tree[cur][0][0][0],tree[cur][0][0][1])+1,min(tree[cur][0][1][0],tree[cur][0][1][1]));
cur=par[cur];
}
update(par3[i],0,0,pre[par3[i]].size()-1,st[i]-st[par3[i]],i);
cur=i;
while(true){
cur=par3[cur];
if(cur==0){
break;
}
dp[par[cur]][0]+=min(min(tree[cur][0][0][0],tree[cur][0][0][1]),min(tree[cur][0][1][0],tree[cur][0][1][1])+1);
dp[par[cur]][1]+=min(min(tree[cur][0][0][0],tree[cur][0][0][1])+1,min(tree[cur][0][1][0],tree[cur][0][1][1]));
cur=par[cur];
// cout<<11<<endl;
update(par3[cur],0,0,pre[par3[cur]].size()-1,st[cur]-st[par3[cur]],cur);
}
}
int cat(int i) {
i--;
it[i]=1;
apply(i);
//dp[i][1]=1e9;
// dfs(0);
int ans=1e9;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ans=min(ans,tree[0][0][i][j]);
}
}
/* for(int i=0;i<n;i++){
cout<<dp[i][0]<<","<<dp[i][1]<<endl;
}*/
//cout<<ans<<endl;
return ans;
}
int dog(int i) {
i--;
it[i]=2;
apply(i);
int ans=1e9;
// cout<<par3[i]<<"::"<<endl;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ans=min(ans,tree[0][0][i][j]);
}
}
/* for(int i=0;i<n;i++){
cout<<dp[i][0]<<","<<dp[i][1]<<endl;
}*/
//cout<<ans<<endl;
return ans;
}
int neighbor(int i) {
it[i-1]=0;
apply(i);
int ans=1e9;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
ans=min(ans,tree[0][0][i][j]);
}
}
/*for(int i=0;i<n;i++){
cout<<dp[i][0]<<","<<dp[i][1]<<endl;
}*/
//cout<<ans<<endl;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
