解き初め JOI 2012春 Building 2

解き納めにするつもりやったのにくだらんバグで6分間に合わんかった…。
典型の組合せで綺麗。好き。
今年は最後の一年やから何事も悔いのないように全力でやり切ります。
難易度12は残り3問。

int N;
int H[100100];
vector<int> up[100100];
vector<int> down[100100];
vector<int> g[100100];
void merge(vector<int> &a,vector<int> &b){
	if(sz(a)<sz(b))swap(a,b);
	for(int i=0;i<sz(b);i++)a[i]=min(a[i],b[i]);
}
int dfs(int v,int p){
	int res = 0;
	for(int i=0;i<g[v].size();i++){
		if(g[v][i]==p)continue;
		int u = g[v][i];
		res = max(res,dfs(u,v));
		bool flag = false;
		if(sz(up[v])>sz(down[u])){
			swap(up[v],down[u]);
			flag = true;
		}
		for(int j=0;j<up[v].size();j++){
			int k = lower_bound(all(down[u]),-up[v][j])-down[u].begin();
			res = max(res,j+k+1);
			if(up[v][j]<(flag?-H[v]:H[v])){
				k = lower_bound(all(down[u]),(flag?H[v]:-H[v]))-down[u].begin();
				res = max(res,j+k+2);
			}
		}
		if(flag)swap(up[v],down[u]);
		flag = false;
		if(sz(up[u])>sz(down[v])){
			swap(up[u],down[v]);
			flag = true;
		}
		for(int j=0;j<up[u].size();j++){
			int k = lower_bound(all(down[v]),-up[u][j])-down[v].begin();
			res = max(res,j+k+1);
			if(up[u][j]<(flag?-H[v]:H[v])){
				k = lower_bound(all(down[v]),(flag?H[v]:-H[v]))-down[v].begin();
				res = max(res,j+k+2);
			}
		}
		if(flag)swap(up[u],down[v]);
		merge(up[v],up[u]);
		merge(down[v],down[u]);
	}
	vector<int>::iterator it;
	it = lower_bound(all(up[v]),H[v]);
	if(it==up[v].end())up[v].pb(H[v]);
	else *it=H[v];
	it = lower_bound(all(down[v]),-H[v]);
	if(it==down[v].end())down[v].pb(-H[v]);
	else *it=-H[v];
	res = max(res,sz(up[v]));
	res = max(res,sz(down[v]));
	return res;
}
int main(){
	scanf("%d",&N);
	for(int i=0;i<N;i++)scanf("%d",&H[i]);
	for(int i=0;i<N-1;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	printf("%d\n",dfs(0,-1));
	return 0;
}