HDU 5325 Crazy Bobo

對原來的邊(u, v) 方向定為u->v當w[u] > w[v]

最大Set是max{u到達的點集合}

 

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

5

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;
}