#include "catdog.h"
typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=100000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
array<array<int,2>,2> comb(array<array<int,2>,2> a,array<array<int,2>,2> b){
array<array<int,2>,2> res;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
res[i][j]=min(min(a[i][0]+b[0][j],a[i][0]+b[1][j]+1),min(a[i][1]+b[0][j]+1,a[i][1]+b[1][j]));
}
}
return res;
}
struct Seg{
int n;
vector<array<array<int,2>,2>>tree;
void build(int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(left==right){
tree[node]={array<int,2>{0,sonsuz*2},array<int,2>{sonsuz*2,0}};
return;
}
build(node*2,left,mid);
build(node*2+1,mid+1,right);
tree[node]=comb(tree[node*2],tree[node*2+1]);
}
void init(int N){
n=N;
tree.resize(n<<2, array<array<int,2>,2>{array<int,2>{0,0},array<int,2>{0,0}});
build();
}
int l,r,c;
void up(int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(left==right){
tree[node][r][r]+=c;
return;
}
if(l>mid)up(node*2+1,mid+1,right);
else up(node*2,left,mid);
tree[node]=comb(tree[node*2],tree[node*2+1]);
}
void update(int tar,int i,int val){
l=tar;
r=i;
c=val;
up();
}
array<array<int,2>,2> qu(int node=1,int left=0,int right=-1){
if(right==-1)right=n-1;
if(left>r||right<l)return array<array<int,2>,2>{array<int,2>{0,2*sonsuz},array<int,2>{2*sonsuz,0}};
if(left>=l&&right<=r)return tree[node];
return comb(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
}
array<array<int,2>,2> query(int lef,int rig){
l=lef;
r=rig;
return qu();
}
};
int n;
int tim=0;
int tip[100001],par[100001],pre[100001],sub[100001],bas[100001],bottom[100001];
Seg seg;
vector<int>komsu[100001];
void dfs1(int pos){
sub[pos]=1;
for(int x:komsu[pos]){
if(x==pre[pos])continue;
pre[x]=pos;
dfs1(x);
sub[pos]+=sub[x];
}
}
void dfs2(int pos){
int mx=-1;
bottom[par[pos]]=pos;
bas[pos]=tim++;
for(int x:komsu[pos]){
if(x==pre[pos])continue;
if(mx==-1||sub[mx]<sub[x])mx=x;
}
if(mx!=-1){
par[mx]=par[pos];
dfs2(mx);
for(int x:komsu[pos]){
if(x==mx||x==pre[pos])continue;
par[x]=x;
dfs2(x);
}
}
}
void initialize(int N,vector<int> A,vector<int> B){
n=N;
for(int i=0;i<n-1;i++){
komsu[A[i]].pb(B[i]);
komsu[B[i]].pb(A[i]);
}
par[1]=1;
dfs1(1);
dfs2(1);
seg.init(tim);
}
void sil(int loc){
if(pre[par[loc]]==0)return;
sil(pre[par[loc]]);
array<array<int,2>,2>sum=seg.query(bas[par[loc]],bas[bottom[par[loc]]]);
seg.update(bas[pre[par[loc]]],0,-min(min(sum[0][0],sum[0][1]),min(sum[1][0],sum[1][1])+1));
seg.update(bas[pre[par[loc]]],1,-min(min(sum[0][0],sum[0][1])+1,min(sum[1][0],sum[1][1])));
}
void op(int loc){
loc=pre[par[loc]];
while(loc){
array<array<int,2>,2>sum=seg.query(bas[par[loc]],bas[bottom[par[loc]]]);
seg.update(bas[pre[par[loc]]],0,min(min(sum[0][0],sum[0][1]),min(sum[1][0],sum[1][1])+1));
seg.update(bas[pre[par[loc]]],1,min(min(sum[0][0],sum[0][1])+1,min(sum[1][0],sum[1][1])));
loc=pre[par[loc]];
}
}
int cat(int v){
sil(v);
seg.update(bas[v],0,sonsuz);
op(v);
tip[v]=1;
array<array<int,2>,2>res=seg.query(bas[1],bas[bottom[1]]);
return min(min(res[0][0],res[0][1]),min(res[1][0],res[1][1]));
}
int dog(int v){
sil(v);
seg.update(bas[v],1,sonsuz);
op(v);
tip[v]=2;
array<array<int,2>,2>res=seg.query(bas[1],bas[bottom[1]]);
return min(min(res[0][0],res[0][1]),min(res[1][0],res[1][1]));
}
int neighbor(int v){
sil(v);
seg.update(bas[v],tip[v]-1,-sonsuz);
op(v);
tip[v]=0;
array<array<int,2>,2>res=seg.query(bas[1],bas[bottom[1]]);
return min(min(res[0][0],res[0][1]),min(res[1][0],res[1][1]));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4688 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
4688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
