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.
易证原题可以等价地转换成找到一个点，只向权值比他大的点走，最多可以走到多少个点。
这样，对于每个点p来说，权值比他大的下一个点q，要不然在他的路径下一个，这样自然满足；否则在另一条路径上，那么这条路径上的所有点至少小于p或q中的一个。又因为p和q的大小关系紧邻，所以小于p，q两个点。
建图的时候只从权值小的向大的连边，然后从每个点开始记忆化搜索，记录每个点能到达的点数即可。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int ans,w[500010],dp[500010],fir[500010],ne[1000010],to[1000010],vis[500010];
int max(int x,int y)
{return x>y?x:y;
}
void add(int fr,int t,int num)
{ne[num]=fir[fr];fir[fr]=num;to[num]=t;
}
void dfs(int x)
{if (vis[x]) return;vis[x]=1;int i,j,k,p,q;dp[x]=1;for (i=fir[x];i;i=ne[i]){dfs(to[i]);dp[x]+=dp[to[i]];}ans=max(ans,dp[x]);
}
int main()
{int i,j,k,m,n,p,q,x,y,z,root;while (scanf("%d",&n)==1){memset(fir,0,sizeof(fir));memset(ne,0,sizeof(ne));memset(dp,0,sizeof(dp));memset(vis,0,sizeof(vis));for (i=1;i<=n;i++)scanf("%d",&w[i]);for (i=1;i<n;i++){scanf("%d%d",&x,&y);if (w[x]<w[y])add(x,y,i);elseadd(y,x,i);}ans=0;for (i=1;i<=n;i++)if (!vis[i])dfs(i);printf("%d\n",ans);}
}