深海龙王和水葫芦娃放了暑假闲的无聊，一天他们路过一棵树，听到树上的知了叫的好欢啊∼
深海龙王准备抓几只知了送给水葫芦娃。他发现面前的这棵树是一颗以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

【NOIP2015模拟10.29B组】抓知了
Description
Input
Output
Sample Input
Sample Output
Data Constraint
solution
code

Data Constraint

【NOIP2015模拟10.29B组】抓知了
Description
Input
Output
Sample Input
Sample Output
Data Constraint
solution
code

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('
'); }
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 }

【NOIP2015模拟10.29B组】抓知了 Description Input Output Sample Input Sample Output Data Constraint solution code