【NOIP2015模拟10.29B组】抓知了

题目大意

深海龙王和水葫芦娃放了暑假闲的无聊，一天他们路过一棵树，听到树上的知了叫的好欢啊∼
深海龙王准备抓几只知了送给水葫芦娃。他发现面前的这棵树是一颗以1 号节点为根节点的一颗有根树，同时他又发现这颗树上的每一个节点i 上都恰好停有一只蝉，正在愉快的以ai 的响声鸣叫∼
深海龙王会从1 号节点起沿着树边一直爬，直到爬到一个叶子节点（请不要在意他怎么下来），在这途中他可以选择一些他经过的蝉并将它们抓起来。但是水葫芦娃希望深海龙王抓的知了能发出越来越响的鸣叫声，起码得要单调不减！
求深海龙王最多能抓到的知了数

解题思路

一看就可以想到最长不下降子序列,正常的算法时间复杂度是(O(n^2))，但是这题要用(O(n exttt{ } log exttt{ } n)),不会请点大佬的详解

接着，我们用(DFS)遍历一下整棵树，在遍历的过程中，把数加到最长不下降子序列。
还要记得回溯！！！

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int tot=0,n,len=1,h[300005],q[300005],a[100005],ans=0,cnt=0,d[100005];

struct edge{
	int to,nxt;
}e[300000];
void add(int x,int y)
{
	e[++tot].to=y;
	e[tot].nxt=h[x];
	h[x]=tot;
}
void dfs(int u)
{
	for (int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].to,flag=0,x,y;
		if (a[v]>=d[len]) d[++len]=a[v],flag=1;
		else
		{
			int l=1,r=len;
			while (l<r)
			{
				int mid=(l+r)>>1;
				if (a[v]>=d[mid]) l=mid+1;
				else r=mid;
			}	
			x=l,y=d[l];
			d[l]=a[v];
		} 
		ans=max(ans,len);
		dfs(v);
		if (flag) len--;
		else d[x]=y;
	}
}
int main()
{
	freopen("cicada.in","r",stdin);
	freopen("cicada.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		int q;
		scanf("%d",&q);
		add(q,i+1);
	}
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	d[1]=a[1];
	dfs(1);
	printf("%d
",ans);
}