Hdu 5325 2015多校对抗赛三

本文主要是介绍Hdu 5325 2015多校对抗赛三，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5325

Crazy Bobo

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

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<wui+1 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<wui .
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

Author

ZSTU

Source

2015 Multi-University Training Contest 3

题目意思：一颗树上有n个节点，由n-1条边连接，每个节点有个权值。

定义一个集合：这个集合内的点按权值小到大排序，要求相连两点路径上的所有点（不包括这两端点）的权值比起始点权值小。

求最大集合的大小。

分析：

对于相连三点：小中大（小到中，中到大，此序列满足要求）

小大中（小到中，路径上有个节点大，不满足要求）

中小大（小到中，满足，中到大，中间有小的节点，但是仍然小于起始节点中，满足）

有以上三种情况，小中大表示点的权值。可见，如果我们把树弄出有向边，那么一定是相对小权值指向相对大权值。

那么，就可以从权最小的节点往外搜，直到外围都是大点。按照上述方式建边，权最小的点的入度一定为0。

最后取个最大值就是答案。

当树是一条链的时候，dfs递归深度很大，需手动扩栈。并且需要记忆化搜索才不会T，所谓记忆化搜索就是标记保存搜索的点的结果，下次碰到此点就不往下搜了。

貌似bfs会T，虽然不会有栈问题，bfs没有记忆搜索。

还有另外一种相对的方法，从最大值节点出发，回到最小值节点，最后取最大值也是答案。但是，建边的话就应该大边指向小边了。

就是从大值节点往小值节点宽搜，一步一步把节点数加到小值节点上面。

#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int w[500001];
int rudu[500001];
int mark[500001];
vector <int> edge[500001];
void dfs(int u,int &cnt){int len=edge[u].size();for(int i=0;i<len;i++){int v=edge[u][i];if(mark[v]!=0)cnt+=mark[v];//记忆化搜索else{int tmp=cnt;dfs(v,++cnt);mark[v]=cnt-tmp;}}
}
void bfs(int u,int &cnt){//没有记忆化搜索queue <int> que;que.push(u);while(!que.empty()){int u=que.front();que.pop();int len=edge[u].size();for(int i=0;i<len;i++){int v=edge[u][i];que.push(v);cnt+=1;}}
}
int main(){int n;while(~scanf("%d",&n)){for(int i=1;i<=n;i++){edge[i].clear();rudu[i]=0;mark[i]=0;scanf("%d",&w[i]);}for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);if(w[a]>w[b]){edge[b].push_back(a);rudu[a]++;}else {edge[a].push_back(b);rudu[b]++;}}int ans=0;for(int i=1;i<=n;i++){int tmp=1;if(rudu[i]==0){dfs(i,tmp);mark[i]=tmp;
//                bfs(i,tmp);//TLEans=max(ans,tmp);}}printf("%d\n",ans);}return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int w[500001];
int rudu[500001];
int cnt[500001];
vector <int> edge[500001];
int main(){int n;while(~scanf("%d",&n)){for(int i=1;i<=n;i++){edge[i].clear();rudu[i]=0;cnt[i]=0;scanf("%d",&w[i]);}queue <int> que;for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);if(w[a]<w[b])swap(a,b);edge[a].push_back(b);rudu[b]++;}for(int i=1;i<=n;i++)if(rudu[i]==0)que.push(i);while(!que.empty()){int u=que.front();que.pop();int len=edge[u].size();for(int i=0;i<len;i++){int v=edge[u][i];cnt[v]+=cnt[u]+1;rudu[v]--;if(rudu[v]==0)que.push(v);}}int tot=0;for(int i=1;i<=n;i++){tot=max(tot,cnt[i]);}printf("%d\n",tot+1);}return 0;
}

这篇关于Hdu 5325 2015多校对抗赛三的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！