A LIS Week
这周只打了ABC165，要说总结题目，就只能说一下F了。
F - LIS on Tree
题意：一个以$1$为根节点的，由$n$个节点的树，第$i$个点的权值为$w_{i}$, 对于每个$k \in [1,n]$,计算从$1$到$k$的最短路径构成的序列的$LIS$的长度。$(1 \leq n \leq 10^5)$
题解：
首先我们先来回顾一下传统$LIS$的计算方法，最暴力的一种是$O(n^2)$的$dp$，在算法竞赛中这种算法基本上是被淘汰了的。最常用的一个算法是利用binary search, 令$dp_{i}$代表长度为$i$的$LIS$结尾的最小的值，初始的时候设置为无穷大。接下来对于每一个$i \in [1,n]$，二分查找第一个大于等于该元素的位置，然后将其替换掉，最终的$LIS$的长度就是最后一个不为$INF$的位置，而这一步我们也可以用二分查找，因此最终时间复杂度为$O(nlog(n))$。这个算法的关键在于二分查找第一个大于等于$w_{i}$的元素并替换掉，这个本质是一种贪心的思想，举个例子：对于数组$\{1,2,5,4,5\}$,当$i=3$时，$dp=\{1,2,5,inf,inf\}$,当$i=4$的时候我们必须要把$dp_{3}$换成$4$，因为后面还有一个$5$。
考虑在树上求$LIS$，其实算法原理基本一致，但是我们唯一要考虑的就是：对于每个节点$u$，我的$dp$数组有效的元素，必须只能包含从$1-u$路径的节点，其他节点不能参与进来，能做到这一点的只有$DFS$，即每次沿着一条路走到底，由于走完后不能影响下一条路径，因此需要$dp $再回溯回去。
代码:
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/*
* @author: codancer
* @createTime: 2020-05-04, 20:44:59
*/
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const ll inf = 1e18;
typedef vector<int> VI;
typedef vector<ll> VII;
typedef pair<int,int> pii;
const int N = 2e5+100;
vector<int> G[N];
ll dp[N],w[N],ans[N];
int n;
void dfs(int u,int fa){
int x=lower_bound(dp,dp+n,w[u])-dp;
ll val=dp[x];
dp[x]=w[u];
ans[u]=lower_bound(dp,dp+n,inf)-dp;
for(int v:G[u]){
if(v==fa) continue;
dfs(v,u);
}
dp[x]=val;
}
int main(){
cin>>n;
rep(i,0,n)dp[i]=inf;
rep(i,0,n-1){
cin>>w[i];
}
int u,v;
rep(i,1,n-1){
cin>>u>>v;
--u;
--v;
G[u].pb(v);
G[v].pb(u);
}
dfs(0,-1);
rep(i,0,n-1) cout<<ans[i]<<endl;
return 0;
}