分析:
疯子树肯定还是一棵树。

所以,所谓的最短路径就是吓唬你的,树上两点之间有且只有一条路径。
b1和b2必须是相邻的,否则不可能是一棵疯子树。
再想一想,用同样的方式构造剩下的点的话,那么可以得到一个结论:
如果以一棵疯子树以键值最小的那个节点为根,那么对于从根到叶的每一条简单路径上,键值是不严格递增的!

所以可以很轻松的得到一个n^2的方法:每个节点作为根dfs一次。计算子树的贡献。

inline void dfs(int x, int fa) {
	f[x] = 1;
	for(int i = h[x]; i; i = E[i].nxt) {
		int v = E[i].to;
		if(v == fa) continue;
		dfs(v, x);
		if(val[x] <= val[v]) f[x] += f[v];
	}
}

main:
int ans = -0x3f3f3f3f;
for(int i = 1; i <= n; i++) dfs(i, 0), ans = max(ans, f[i]);
printf("%d\n", ans);

n^2只能骗分。

正确思路:我们就可以用树形dp求以每个节点为根,的最多不严格递增简单路径的节点个数,

void dfs1(int u, int fa){


    f[u]=1;
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to!=fa){
            dfs1(to, u);
            if(w[to]>=w[u]){
                f[u]+=f[to];
            }
        }
    }
}

这个时候没有考虑这个节点的父亲节点上的不严格递增简单路径的节点个数的贡献。
所以我们必须要把这个加上。这个地方需要二次扫描。
我们再dfs一次

void dfs2(int u, int fa){


    if(w[fa]>=w[u]){
        f[u]+=f[fa];
    }
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to!=fa){
            dfs2(to, u);
        }
    }
}

我们来证明一下这个二次扫描的正确性:


那么f[v]的贡献只来自黄色,f[u]的贡献只来自红色。因为w[v]<=w[u]所以求v为根节点最大疯子树,u和v可以连起来。f[v]+=f[u]就是以v为根节点的最大疯子树个数。

如果w[v]>w[u], u不对v产生贡献,f[v]就是答案。
其于节点以此类推。证明完毕。

#include<bits/stdc++.h>
using namespace std;

int w[200005];
vector<int> v[200005];
int f[200005]={0};
int d[200005]={0};
void dfs1(int u, int fa){


    f[u]=1;
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to!=fa){
            dfs1(to, u);
            if(w[to]>=w[u]){
                f[u]+=f[to];
            }
        }
    }
}

void dfs2(int u, int fa){


    if(w[fa]>=w[u]){
        f[u]+=f[fa];
    }
    for(int i=0; i<v[u].size(); i++){
        int to=v[u][i];
        if(to!=fa){
            dfs2(to, u);
        }
    }
}

int main()
{
    int n, u, to;
    freopen("crazy6.in", "r", stdin);
    while(~scanf("%d", &n)){
        for(int i=1; i<=n; i++){
            v[i].clear();
            f[i]=0,d[i]=0;
            scanf("%d", &w[i]);
        }
        for(int i=1; i<n; i++){
            scanf("%d%d", &u, &to);
            v[u].push_back(to);
            v[to].push_back(u);
        }
        dfs1(1, 0);
        dfs2(1, 0);
        int ans=-1;
        for(int i=1; i<=n; i++){
            ans=max(ans, d[i]+f[i]);
        }
        printf("%d\n", ans);
    }

	return 0;
}