|
对原来的边(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; }
?
?
|