AtCoder Beginner Contest 165 F - LIS on Tree 문제풀이(dfs + 최장 상승 하위 시퀀스 2점 방식)

제목 링크

제목의 대의.

나무 한 그루를 드릴게요. 정점 1부터 다른 모든 정점까지의 최장 상승자 서열을 구하세요.

제목 사고방식

나는 원래lca라고 생각했는데 쓸 수 없을 것 같아서 결과는 dfs면 된다. 그리고 거슬러 올라가면 일반적인 최장 상승자 서열과 큰 차이가 없다.

코드

#include
#include
#include
using namespace std;
const int maxn=2e5+5;
int n,a[maxn],head[maxn],cnt,dp[maxn],ans[maxn];
struct node{
    int to,next;
}e[maxn<<1];
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int son,int fa){
    int pos=lower_bound(dp+1,dp+1+n,a[son])-dp;
    int temp=dp[pos];//      
    dp[pos]=a[son];
    ans[son]=max(ans[fa],pos);//     
    for(int i=head[son];i;i=e[i].next){
        if(e[i].to!=fa){
            dfs(e[i].to,son);
        }
    }
    dp[pos]=temp;//  
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1,u,v;i<=n-1;i++){
        scanf("%d %d",&u,&v);
        add(u,v),add(v,u);
    }
    memset(dp,0x3f,sizeof(dp));
    dfs(1,0);
    for(int i=1;i<=n;i++){
        printf("%d
",ans[i]);
    }
    return 0;
}