[ABC165F] LIS on Tree

题目

题目链接

题目大意：给出一棵 $n$ 个点的树，每个点有点权。对每个点求出从 $1$ 号点到第 $i$ 号点路径上最长的 LIS 长度。$1 \le n \le 2 \cdot 10^5$。

思路

先考虑序列上的做法，只需要 $O(n \log n)$ 求 LIS 就行了。

树上求 LIS 的方法也类似，对于每个点二分该元素在 LIS 里的位置更新答案，就是要加一个回溯的过程。

注意求的并不是第 $i$ 个点的 LIS 而是这条路径上最大的 LIS，所以要对父亲求最大值。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

std::vector<int> g[200010];
int a[200010], f[200010], b[200010];
int n, l;

void dfs(int now, int pa) {
    int p, r;
    bool flag = false;
    if (a[now] > b[l]) {
        b[++l] = a[now];
        f[now] = l;
    } else {
        flag = true;
        p = std::lower_bound(b + 1, b + l + 1, a[now]) - b;
        r = b[p];
        b[p] = a[now];
        f[now] = std::max(f[pa], p);
    }
    for (auto i : g[now]) {
        if (i != pa) {
            dfs(i, now);
        }
    }
    if (flag)	b[p] = r;
    else	b[l--] = 0;
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i)	read(a[i]);
    for (int i = 1, u, v; i < n; ++i) {
        read(u), read(v);
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i)	printf("%d\n", f[i]);
    return 0;
}