Crazy Bobo

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 382 Accepted Submission(s): 116

Problem Description Bobo has a tree,whose vertices are conveniently labeled by 1,2,...,n.Each node has a weight wi . All the weights are distrinct.
A set with m nodes v1,v2,...,vm is a Bobo Set if:
- The subgraph of his tree induced by this set is connected.
- After we sort these nodes in set by their weights in ascending order,we get u1,u2,...,um ,(that is, wui for i from 1 to m-1).For any node x in the path from ui to ui+1 (excluding ui and ui+1 ),should satisfy wx .
Your task is to find the maximum size of Bobo Set in a given tree.

Input The input consists of several tests. For each tests:
The first line contains a integer n ( 1≤n≤500000 ). Then following a line contains n integers w1,w2,...,wn ( 1≤wi≤109 ,all the wi is distrinct).Each of the following n-1 lines contain 2 integers ai and bi ,denoting an edge between vertices ai and bi ( 1≤ai,bi≤n ).
The sum of n is not bigger than 800000.

Output For each test output one line contains a integer,denoting the maximum size of Bobo Set.
Sample Input

7
3 30 350 100 200 300 400
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output

Source 2015 Multi-University Training Contest 3

#pragma comment(linker, /STACK:1024000000,1024000000)
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; typedef long long ll; #define prt(k) cout<<#k = <
      
        w[v]) g[u] = up(v) + 1; return g[u]; } int n; pair
       
         p[N]; int main() { while (scanf(%d, &n)==1) { for (int i=1;i<=n;i++) scanf(%d, w+i), p[i]=make_pair(w[i], i); sort(p+1, p+n+1); mm = 0; memset(head, -1, sizeof head); for (int i=0;i
        
         =1;i--) { int u = p[i].second; dp[u] = 1; for (int j=head[u];~j;j=e[j].next) { int v = e[j].v; if (w[u] < w[v]) dp[u] += dp[v]; } ans = max(ans, dp[u]); } printf(%d , ans); } return 0; }

HDU 5325 Crazy Bobo

Crazy Bobo