F - LIS on Tree（LIS&DFS）

题目传送门

题意：给定一棵树，求所有结点到根结点的长度。

思路：显然根据的贪心思想，我们可以对其在树上进行操作，与普通的不同的是，一开始我们可以将存

放的数组进行初始化为,这样每次只需要进行二分操作就行了，省去了直接添加到数组末尾的那一步。由于

不同的路径是不同的，所以每次搜索完一个结点就要回溯，还原到之前的数组。

这样问题就解决了。

时间复杂度：

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct edge{
    int to,nt;
}e[N<<1];
int ans[N],d[N],a[N],cnt=1,h[N],n;//ans[i]存放答案,d[i]表示LIS数组 
void add(int u,int v){
    e[cnt]={v,h[u]};
    h[u]=cnt++;
}
void dfs(int u,int fa){
    int p=lower_bound(d+1,d+n+1,a[u])-d;//基于LIS的贪心思想 
    int tmp=d[p];
    d[p]=a[u];
    ans[u]=max(ans[fa],p);//取最大值. 
    for(int i=h[u];i;i=e[i].nt)
    {
         int v=e[i].to;
         if(v==fa) continue;
         dfs(v,u);
    }
    d[p]=tmp;//回溯,因为不同子树的LIS路径不同. 
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,u,v;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    memset(d,0x3f,sizeof d);
    dfs(1,0);
    for(int i=1;i<=n;i++)
        printf("%d\n",ans[i]);
    return 0;
}