【NOIP2015模拟10.29B组】抓知了

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

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