社区讨论
刚学OI,不是女生,求dalao帮忙看
P3365改造二叉树参与者 13已保存回复 19
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 19 条
- 当前快照
- 1 份
- 快照标识符
- @mi7cl52i
- 此快照首次捕获于
- 2025/11/20 19:28 4 个月前
- 此快照最后确认于
- 2025/11/20 21:57 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define rg register
#define il inline
#define MAXN 100005
il int fr(){
rg int f=1,res=0;rg char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=res*10+ch-'0';ch=getchar();}
return f*res;
}
using namespace std;
struct node{
LL date;
node *ls,*rs;
}tree[MAXN];
LL n;
LL fa,ch;
LL a[MAXN],f[MAXN],d[MAXN];
LL cnt=0,len;
il void in(){
n=fr();
for(rg LL i=1;i<=n;++i)tree[i].date=fr();
for(rg LL i=1;i<=n-1;++i){
fa=fr();ch=fr();
if(ch==0)tree[fa].ls=&tree[i+1];
else tree[fa].rs=&tree[i+1];
}
return;
}
il void zxdfs(node *x){
if(x!=NULL){
zxdfs(x->ls);
++cnt;
a[cnt]=x->date-cnt;
zxdfs(x->rs);
}
return;
}
il LL erf(rg LL x){
rg LL l=1,r=len,ans=0;
while(l<=r){
LL mid=(l+r)>>1;
if(a[mid]<=x)ans=mid,l=mid+1;else r=mid-1;
}
return ans;
}
il void bxj(){
for(rg int i=1;i<=n;++i){
f[i]=erf(a[i])+1;
d[f[i]]=a[i];
len=len>f[i]?len:f[i];
}
}
int main(){
in();
zxdfs(&tree[1]);
// for(rg LL i=1;i<=n;++i)printf("%lld ",a[i]);
bxj();
// printf("%lld\n",len);
printf("%lld",n-len);
return 0;
}
回复
共 19 条回复,欢迎继续交流。
正在加载回复...