LIS 可以用 BIT 维护，但是 BIT 不支持撤销，所以我们改成线段树。

然后我们就根据值域开栈再 dfs，如果以当前节点为末尾的 LIS 长度超过了栈顶就入栈，遍历完字数后再弹出。

记得离散化。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
struct SMTree
{
	struct node{int l,r,mx;}tr[N<<2];
	void pushup(int p){tr[p].mx=max(tr[lc(p)].mx,tr[rc(p)].mx);}
	void bt(int p,int l,int r)
	{
		tr[p]={l,r,0};
		if(l==r)return;
		int mid=(l+r)>>1;
		bt(lc(p),l,mid);bt(rc(p),mid+1,r);
		pushup(p);
	}
	void change(int p,int x,int k)
	{
		if(tr[p].l>x||tr[p].r<x)return ;
		if(tr[p].l==tr[p].r)
		{
			tr[p].mx=k;
			return;
		}
		change(lc(p),x,k);change(rc(p),x,k);
		pushup(p);
	}
	int query(int p,int l,int r)
	{
		if(tr[p].l>r||tr[p].r<l)return 0;
		if(l<=tr[p].l&&tr[p].r<=r)return tr[p].mx;
		return max(query(lc(p),l,r),query(rc(p),l,r));
	}
}tr;
vector<int>G[N];
int a[N],ans[N],c[N],b[N];stack<int>stk[N];
void dfs(int x,int f)
{
	c[x]=tr.query(1,1,a[x]-1)+1;
	ans[x]=max(c[x],ans[f]);
	bool bk=0;
	if(ans[x]>stk[a[x]].top())
	{
		stk[a[x]].push(c[x]);
		tr.change(1,a[x],stk[a[x]].top());
		bk=1;
	}
	for(int y:G[x])if(y!=f)
		dfs(y,x);
	if(bk)stk[a[x]].pop(),tr.change(1,a[x],stk[a[x]].top());
}
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);int blen=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+blen+1,a[i])-b; 
	for(int i=1;i<n;i++)
	{
		int x,y;cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i=1;i<=blen;i++)stk[i].push(0);
	tr.bt(1,1,blen);
	dfs(1,0);
	for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
	return 0;
}