#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"
llo x;
vector<llo> adj[100001];
llo dp[100001][2];
llo it[100001];
llo par[100001];
llo ss[100001];
llo st[100001];
llo par3[100001];
llo n;
vector<vector<vector<llo>>> tree[100001];
vector<llo> pre[100001];
void dfs(llo no,llo par2=-1){
ss[no]=1;
par[no]=par2;
vector<pair<llo,llo>> 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();
}
}
llo co=0;
void dfs2(llo no,llo 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<llo> kk;
kk.pb(0);
kk.pb(0);
vector<vector<llo>> ll;
ll.pb(kk);
ll.pb(kk);
for(llo i=0;i<4;i++){
tree[par3[no]].pb(ll);
}
for(auto j:adj[no]){
if(j!=par2){
dfs2(j,no);
}
}
}
void build(llo ind,llo no,llo l,llo r){
if(l==r){
tree[ind][no][0][0]=0;
tree[ind][no][1][1]=0;
tree[ind][no][1][0]=1e6;
tree[ind][no][0][1]=1e6;
}
else{
llo mid=(l+r)/2;
build(ind,no*2+1,l,mid);
build(ind,no*2+2,mid+1,r);
}
}
void update(llo ind,llo no,llo l,llo r,llo i,llo 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]=1e6;
}
if(it[j]==1){
tree[ind][no][1][1]=1e6;
}
// cout<<j<<","<<tree[ind][no][0][0]<<","<<tree[ind][no][1][1]<<endl;
tree[ind][no][1][0]=1e6;
tree[ind][no][0][1]=1e6;
}
else{
llo 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]=1e6;
tree[ind][no][1][1]=1e6;
tree[ind][no][1][0]=1e6;
tree[ind][no][0][1]=1e6;
for(llo i=0;i<2;i++){
for(llo j=0;j<2;j++){
for(llo l=0;l<2;l++){
for(llo k=0;k<2;k++){
llo 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(llo 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(llo i=0;i<n;i++){
if(pre[i].size()){
build(i,0,0,pre[i].size()-1);
}
}
for(llo i=0;i<n;i++){
it[i]=0;
dp[i][0]=0;
dp[i][1]=0;
}
}
void apply(llo i){
//<llo> xx;
llo 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]=1e6;
// dfs(0);
llo ans=1e6;
for(llo i=0;i<2;i++){
for(llo j=0;j<2;j++){
ans=min(ans,tree[0][0][i][j]);
}
}
/* for(llo 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);
llo ans=1e6;
// cout<<par3[i]<<"::"<<endl;
for(llo i=0;i<2;i++){
for(llo j=0;j<2;j++){
ans=min(ans,tree[0][0][i][j]);
}
}
/* for(llo i=0;i<n;i++){
cout<<dp[i][0]<<","<<dp[i][1]<<endl;
}*/
//cout<<ans<<endl;
return ans;
}
int neighbor(int i) {
i--;
it[i]=0;
apply(i);
llo ans=1e6;
for(llo i=0;i<2;i++){
for(llo j=0;j<2;j++){
ans=min(ans,tree[0][0][i][j]);
}
}
/*for(llo 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 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
7284 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
7284 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7356 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 6 |
Incorrect |
4 ms |
7284 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
