LIS on Tree题解

· · 题解

AT5392 题解

前置知识：树形结构、线性 DP

考验读题能力的一道好题。题目大意很简单，就是把一个简单的线性 DP 移植到了树上。

但是这道题有一个难点：即给定的树是一棵无根树，也就是说边是无向的。所以说在输入时应该建立一条双向的边。

参考下面的一段错误代码：

for (int i = 1; i < n; i++) {
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
    }
/*可以看到在输入时没有在y->x方向上建边*/

至于最长上升子序列，在遍历树时打一个记忆化搜索就可以，萌新可以参考下面的DP状态转移方程：

DP[i] = \max(DP[j]+1)

其中 j 满足 a[j]<a[i]。直接枚举的暴力思路在算法竞赛中很常见，但是在这道题中显然不适用，因为 n \leq 2 \times 10^5，同时又有数据结构的限制。

因此我们要在原来状态的基础上做一个优化。引入 LIS 问题的优化算法--二分法。这种算法刚开始可能很难理解，它在原先的状态转移方程的基础上进行了改动。考虑贪心的思想，优先选择较小的数可以使后来增加的数的取值变小，意味着我们可以选择更多的数，可以构造出一个符合条件的序列，让序列的长度表示当前 LIS 的长度。当一个新数加入时，用二分法查看它能够在原序列中替换的位置，这里的“替换”是暂时的，并不是当前的序列。真正的序列应该取决于当前序列的最后一个元素，只有这个数改动，才意味着序列发生了变化。

最后我们根据构造好的最终“序列”的长度，判断出 LIS 的长度。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n, x, y, a[200005], dp[200005], f[200005], tot, ans;
//tot表示当前序列的长度
//f[i]表示以i为一棵子树的根时，序列的长度 
vector<int> G[200005];
//用邻接表表示树 
bool vis[200005];
//vis判断是否走过，因为是无向边 
void dfs(int rt){//因为我们的目的是找一条链，所以用DFS遍历，同时方便记忆化。 
    vis[rt] = 1;
    ans = max(ans, tot);
    int l, r, t, mid;
    bool flag = 0;
    if (!tot || a[rt] > dp[tot]) dp[++tot] = a[rt], flag = 1;
    //判断能否在序列的末尾增加新元素
    //如果可以则加入，并将序列长度增加一 
    else{
        l = 1, r = tot;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (dp[mid] >= a[rt])
                r = mid - 1;
            else
                l = mid + 1;
        }
        t = dp[l];
        dp[l] = a[rt];
        //否则就在原序列中“替换”一个数
        //此时“序列”长度不变 
    }
    f[rt] = tot;
    for (int i = 0; i < G[rt].size(); i++)
        if (!vis[G[rt][i]]) dfs(G[rt][i]);
    //对下一个节点进行遍历 
    if (flag) dp[tot] = 0, tot--;
    else dp[l] = t; 
    //在回溯时撤回当前的操作 
}
int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i < n; i++){
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);//正确的建树方法 
    }
    dfs(1);//dfs遍历树 
    for (int i = 1; i <= n; i++)
        printf("%d\n", f[i]);//按要求输出 
    return 0;
}