0%

[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,所以要对父亲求最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#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;
}