On July 16, 2020, T4 [NOIP2015 simulation group 10.29B] learned (jz summer training day2)

Description

The Dragon King of the deep sea and the water hyacinth baby spent their summer holidays idly. One day, they passed by a tree and heard cicadas shouting on the tree. They were so happy
The Dragon King of the deep sea is going to catch some cicadas and give them to the water Cucurbita. He found that the tree in front of him was a rooted tree with node 1 as the root node. At the same time, he found that there was a cicada on every node i of the tree, which was chirping happily with the sound of ai
The deep sea dragon king will climb along the edge of the tree from node 1 until he reaches a leaf node (please don't care how he gets down). On the way, he can select some cicadas he passes and catch them. But the water hyacinth baby hopes that the cicada captured by the deep-sea Dragon King can make more and more loud calls, at least monotonously!

Input

The first line contains an integer n, indicating the number of nodes on the tree;
The second line contains n − 1 integers, representing the parent node numbers of nodes 2 to n respectively;
The third line contains n integers ai, representing the sound of node i knowing.

Output

An integer in one line indicates the maximum number of knowledge that the Dragon King of the deep sea can catch.

Sample Input

11
1 1 1 2 2 6 7 3 3 10
6 5 2 2 6 4 3 2 10 2 3

Sample Output

3

Er, er, if the data range is n<=100000, I don't want to get the graph

Race time

There will be 20 seconds left after T3, so...... Not done

Positive solution

The longest subsequence on the tree doesn't drop. Just let you find the length, and you don't need the n-square. There is an nlog(n) algorithm. This one has a drawback that it can't print, but the title doesn't let you print, so do it.
For this algorithm, first add an array b (without descending) to store the number, and then the general method is as follows:
If you encounter a number > =b, the last bit of the array will be saved directly.
If this number is less than the last digit, then find the first number (successor) in b that is larger than it and replace it. You can use two points for this.
Keep repeating the above process. The final length is the answer, but the number in b is disordered (it's useless to put it bluntly)
So why? Although the last number is not correct, their relative positions are unchanged, so I don't know the rest. If it is proved nlogn algorithm of longest non descending subsequence That's it.
The rest is done on the tree. In fact, they are exactly the same. Pay attention to backtracking. In addition, a[i] may be a negative number, and b should initialize infinitesimal, otherwise 95 points will lead to a point of death.

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 100007
#define INF 0x3f3f3f3f
using namespace std;
int n,len,maxn,a[N],b[N];
int f[N],head[N<<3],cnt;
struct node{
	int to,nxt;
}e[N<<1];
void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void dfs(int x){
	if(b[len]<=a[x]){
		b[++len]=a[x];
		for(int i=head[x];i;i=e[i].nxt)
			if(e[i].to!=f[x])dfs(e[i].to);
		maxn=max(maxn,len);
		b[len]=0;
		len--;
	}else{
		int l=1,r=len,mid=0;
		while(l<r){
			mid=l+r>>1;
			if(b[mid]>a[x])
				r=mid;
			else l=mid+1;
		}
		int t=b[r];
		b[r]=a[x];
		for(int i=head[x];i;i=e[i].nxt)
			if(e[i].to!=f[x])dfs(e[i].to);
		maxn=max(maxn,len);
		b[r]=t;
	}	
}
int main(){
	freopen("cicada.in","r",stdin);
	freopen("cicada.out","w",stdout);
	memset(b,-INF,sizeof(b));
	scanf("%d",&n);
	int x;
	for(int i=2;i<=n;i++)
		scanf("%d",&x),add(x,i),add(i,x),f[i]=x;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	dfs(1);
	printf("%d",maxn);
}

Nothing to say???

Posted by ted_chou12 on Mon, 30 May 2022 20:24:11 +0530