P3365 改造二叉树

L2575645259 · 2019-01-25 11:50:31 · 个人记录

include<bits/stdc++.h>

define For(i,j,k) for(int i=j;i<=k;i++)

define Dow(i,j,k) for(int i=k;i>=j;i--)

define ll long long

using namespace std; inline ll read() { ll t=0,f=1; char c=getchar(); while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();} while(isdigit(c)) t=t10+c-'0',c=getchar(); return tf; } inline void write(ll x) { if(x<0) {x=-x;putchar('-');}if(x>=10)write(x/10);putchar(x%10+'0');} inline void writeln(ll x) { write(x); puts("");} inline void write_p(ll x) { write(x); putchar(' ');}

int ls[100005],rs[100005],u; ll fre[100005],ed[100005]; inline void dfs(int x) { if(ls[x]!=0) dfs(ls[x]); ed[++u]=fre[x]; if(rs[x]!=0) dfs(rs[x]); } int main() { int n;cin>>n; For(i,1,n) fre[i]=read(); For(i,2,n) { ll a=read(),b=read();if(b==0) ls[a]=i;if(b==1) rs[a]=i; } dfs(1); memset(fre,0,sizeof(fre)); For(i,1,n) ed[i]-=i; u=1;fre[u]=ed[u]; For(i,2,n) { if(ed[i]>=fre[u]) {fre[++u]=ed[i];continue;} int j=0,l=1,r=u; while(l<=r) { int mid=(l+r)>>1; if(fre[mid]>ed[i]) j=mid,r=mid-1; else l=mid+1; } fre[j]=ed[i]; } printf("%d",n-u); return 0; }