Algorithms Weekly 7

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
    */
    #include<bits/stdc++.h>

    using namespace std;
    typedef long long ll;
    const ll mod = 1e9+7;
    const ll inf = 1e18;
    #define pb push_back
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    #define rep(i,a,b) for(int i=(a);i<=(b);i++)
    #define fep(i,a,b) for(int i=(a);i>=(b);i--)
    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;
    }