@ysner
2018-05-19T16:51:29.000000Z
字数 1301
阅读 2040
DP
给定一颗带点权的二叉树,询问把它修改成每个点至少需要改几个数。
戳我
此题就是询问一颗树中序遍历的最长不下降子序列。
但注意到每两个数差至少为(否则插不进数)。
有个小技巧是把原数列转化为。
Update:标准模板
// luogu-judger-enable-o2
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
struct node{int w,id;}t[N];
int n,son[2][N],dp[N],top,cnt,lin[N];
il int gi()
{
re int x=0,t=1;
re char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') t=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
return x*t;
}
il void wri(re int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) wri(x/10);
putchar(x%10+'0');
}
bool cmp(node a,node b){return a.id<b.id;}
il void dfs(re int u)
{
if(son[0][u]) dfs(son[0][u]);
lin[++cnt]=t[u].w-cnt;
if(son[1][u]) dfs(son[1][u]);
}
int main()
{
n=gi();
fp(i,1,n) t[i].w=gi();
fp(i,2,n)
{
re int x=gi(),y=gi();
son[y][x]=i;
}
dfs(1);
fp(i,1,n)
{
if(!top||dp[top]<=lin[i]) dp[++top]=lin[i];
else dp[lower_bound(dp+1,dp+top+1,lin[i])-dp]=lin[i];
}
printf("%d\n",n-top);
fclose(stdin);
fclose(stdout);
return 0;
}