本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
Description
深海龙王和水葫芦娃放了暑假闲的无聊，一天他们路过一棵树，听到树上的知了叫的好欢啊∼
深海龙王准备抓几只知了送给水葫芦娃。他发现面前的这棵树是一颗以1 号节点为根节点的一颗有根树，同时他又发现这颗树上的每一个节点i 上都恰好停有一只蝉，正在愉快的以ai 的响声鸣叫∼
深海龙王会从1 号节点起沿着树边一直爬，直到爬到一个叶子节点（请不要在意他怎么下来），在这途中他可以选择一些他经过的蝉并将它们抓起来。但是水葫芦娃希望深海龙王抓的知了能发出越来越响的鸣叫声，起码得要单调不减！
Input
第1 行包含一个整数n，表示树上的结点个数;
第2 行包含n − 1 个整数，分别代表第2 至n 号节点的父亲节点编号；
第3 行包含n 个整数ai，代表i 号节点知了的响声。
Output
一行一个整数，表示深海龙王最多能抓到的知了数。
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
Data Constraint
solution
咕了好几天这道题。
就是树上求最长不下降子序列，注意子序列可以不连续
dfs扫每个可能的序列，取最大值即可
记得回溯！
code
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 #include<algorithm>
5 #include<cstring>
6 #include<queue>
7 #include<vector>
8 #include<stack>
9 #include<set>
10 #include<bitset>
11 #include<map>
12 using namespace std;
13
14 template <typename T> void read(T &x) {
15 x = 0; int f = 1; char c;
16 for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') f = -f;
17 for (; c >= '0' && c <= '9'; c = getchar()) x = 10 * x + c - '0' ;
18 x *= f;
19 }
20 template <typename T> void write(T x){
21 if (x < 0) putchar('-'), x = -x;
22 if (x > 9) write(x / 10);
23 putchar(x % 10 + '0');
24 }
25 template <typename T> void writeln(T x) { write(x); putchar('\n'); }
26
27 #define int long long
28 #define inf 1234567890
29 #define next net
30 #define P 1000000007
31 #define N 202000
32 #define lson (o<<1)
33 #define rson (o<<1|1)
34 #define R register
35
36 int n,len = 1,cut,ans;
37 int ver[N ],head[N ],next[N ];
38 int a[N ],d[N ];
39 void add(int x,int y)
40 {
41 ver[++cut] = y; next[cut] = head[x]; head[x] = cut;
42 }
43 void dfs(int x)
44 {
45 for(R int i = head[x]; i; i = next[i])
46 {
47 int y = ver[i], book = 0, aa, bb;
48 if(a[y] >= d[len]) d[++len] = a[y], book = 1;
49 else
50 {
51 aa = upper_bound(d + 1, d + len + 1, a[y]) - d;
52 bb = d[aa];
53 d[aa] = a[y];
54 }
55 ans = max(ans,len);
56 dfs(y);
57 if(book) len--;
58 else d[aa] = bb;
59 }
60 }
61 signed main()
62 {
63 freopen("cicada.in","r",stdin);
64 freopen("cicada.out","w",stdout);
65 read(n);
66 for(R int i = 2, x; i <= n; i++)
67 {
68 read(x);
69 add(x,i);
70 }
71 for(R int i = 1; i <= n; i++) read(a[i]);
72 d[1] = a[1];
73 dfs(1);
74 writeln(ans);
75 return 0;
76 }
