题目链接：OpenJudge - 1:List
最近做的东西更有挑战性了。ゆっくりして、慢慢地学也挺有意思。

题目

总时间限制: 10000ms　单个测试点时间限制: 1000ms　内存限制: 512000kB
描述
银河战舰DK战队准备在T国组织一系列水友赛。T国有n个城市，n-1条双向航线，所有城市可以互相到达。DK战队正在规划行程，他们可以从任意一个城市开始，也可以在任意一个城市结束，但是整个路线不可以经过同一个城市两次，即每次到达一个新城市，离开后就再也不会回到这个城市，也不能再经过这个城市到达别的城市（否则肯定会回到这个城市）。另外，DK战队并不需要在每个经过的城市举行水友赛，他们发现每个城市有一个DK战队的人气指数，于是决定每次举行水友赛的城市，人气指数一定要严格高于上一次举行水友赛时的城市的人气指数。DK战队想知道在这些条件下，最多可以举行几场水友赛。

输入
第一行一个整数 n，表示城市数。第二行 n 个整数 r1...rn，表示每个城市的人气指数。接下来 n-1 行，每行两个整数 a, b，表示城市 a 与 b 之间有一条双向航线。
对于 10% 的数据，b = a + 1
对于另 20% 的数据，n <= 6000
对于另 30% 的数据，n <= 50000
100% 的数据，2 <= n <= 200000, 1 <= ri <= 10^6
输出
1 行答案。

样例输入 1

样例输出 1

样例输入 2

6
1 2 3 4 5 1
1 2
2 3
3 4
3 5
3 6

样例输出 2

思路

这个题的大意可以用一句话道清：求一棵树上的最长上升子序列.
更精确地说，我们需要按照一种一般的树式拓扑次序（而非平凡的线性次序）遍历一个数据集，求出经过的最长上升子序列的长度. 因此这是普通最长上升子序列（Longest Increasing Subsequence, LIS）问题的一种推广.
尽管题意简短，这道题完全不简单. 为了理解它的高效率算法的原理，我花了小半个周末去搞懂线段树这个东西，并且开始接触一些更 sophisticated 的数据结构等技术.
在此之前我只知道线段树是用来存放区间内信息的一种数据结构，这个问题给我提供了一些对其作用的感知. 网上有两三篇此题的解，但不好懂. 我争取在这里把想明白的说清.

首先回想一下求线性序列 $\{a_n\}_{n=0}$ 的 LIS 的最快算法是怎样的.

$O(2^n)$ ：列出所有子序列的穷举算法时间复杂度为 $O(2^n)$ .

$O(n^2)$ ：常规的动规算法是给子问题增限，令 $M(k)$ 表示以位置 $k$ 的元素结束的最长上升子序列长度，则 $M(i)=max\{M(t)\ |\ 0\leq t<i\ \wedge \ a_t<a_i\}+1$ . 所求答案为 $max\{M(i)\ |\ 0\leq i<n \}$ . 每次迭代需要线性枚举 $t$ ，复杂度为 $O(n^2)$ .

$O(n \log n)$ ：为了得到更好的效率，可以在每一步的大小比较上节省时间.
我们先考虑动态建立一棵二叉搜索树（BST），节点的键值为 $a_k$ ，信息值为以位置 $k$ 的元素结束的最长上升子序列长度，每次迭代添上当前位置的对应节点. BST 的便利是可以在 $O(\log n)$ 时间内找到键值小于当前 $a_i$ 的最大项，但是不足以解决问题，因为我们需要知道所有键值小于当前 $a_i$ 的项中最大的信息值（并加上 $1$ ）. 简单的 BST 不足以获取这个信息.

有两种解决这个问题的路子.

第一种方法比较巧妙，是以贪心策略动态维护以每个位置结束的 LIS. 为什么？此方法的观察是，我们迭代时之所以必须对所有更小的前项找最大 LIS 长，是因为我们缺乏对整个 LIS 结构的了解. 我们完全可以在迭代到每个位置时，花常数时间把递推关系中的 $+1$ （append 操作）应用于所建的 LIS 里. 我们贪心的策略将保证这种 append 方法最优，避免了遍历所有更小前项带来的开销. 具体的贪心方式是这样的：线性遍历 $i$ ，对当前位置 $i$ ，寻找此前 LIS 中小于 $a_i$ 的最右侧元素 $a_{t_0}$ （由于 LIS 递增，可用二分查找达到 $O(\log n)$ 开销），并将其后的部分 $LIS[t_0+1...]$ 截掉，替换为 $a_i$ （如果其后为空则直接 append $a_i$ ）. 如此一来，此前 LIS 中最左侧的不小于 $a_i$ 的元素一定会减小或不变，这有利于后面的元素进入 LIS. 当然，如果直接截掉，会丢失此前 LIS 右边的信息，因此我们只把位置 $LIS_{t_0+1}$ 换成 $a_i$ . 由此逻辑得到的序列不一定是 LIS 本身，但其长度和最右一个元素一定和正确的 LIS 一致. 我们给这个序列换个名字， $approx$ （“近似”）.
贪心算法的时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$ .
贪心算法的代码如下.

using namespace std;

typedef int TYPE; 

int size;
vector<TYPE> seq;
vector<TYPE> LIS_approx;

int LIS_length(){
    LIS_approx.push_back(seq[0]);
    for(int i=1; i<size; ++i){
        if(seq[i]>LIS_approx.back())
            LIS_approx.push_back(seq[i]);
        else{
            auto it = lower_bound(LIS_approx.begin(), LIS_approx.end(), seq[i]);
            *it = seq[i];
        }
    }
    return LIS_approx.size();
}

第二种方法的考虑更加直接. 由于每次要获取所有键值小于当前 $a_i$ 的项中最大的信息值，故这是一个询问区间属性最值的问题. 维护区间属性值，我们有数据结构利器——线段树. 对于此问题，在应用线段树之前还需要一步转化. 「所有键值小于当前 $a_i$ 的项中最大的信息值」如何转化成「所有某个区间内的项最大的信息值」？考虑键值小于 $k$ 即为在序列中自小到大的排名小于 $k$ ，可用各 $a_k$ 在升序排序后的排名 $order(k)$ 代替 $a_k$ 作为线段树的区间量度（即键值. 此处一个细节是，严格的 LIS 前后的元素不能相等，故等值的 $a_k$ 排名随下标应当不增，一种实施方法是排序后去重）. 在遍历到位置 $i$ 时，只需查询区间 $[0,order(i)-1]$ 里的最大信息值，加 $1$ 后插入线段树即可. 最终答案为整区间的最大值.
线段树算法的时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$ .
线段树算法的参考代码如下. 我喜欢用指针建树，另外这里是一次性建完整，没有动态创点.

using namespace std;

typedef int TYPE;

class segtree{
    public:
        int left, right;
        int val;
        segtree *L, *R;
        void create(int lower, int upper, int init);
        void update(int pos, int new_val);
        int query(int start, int end);
        void wipe();
};

int size;
vector<TYPE> seq, sorted;
vector<int> order;

void segtree::create(int lower, int upper, int init = 0){
    left = lower; right = upper; val = init;
    L = R = nullptr;
    if(left==right) return;
    int mid = (left+right)>>1;
    auto LT = new segtree; LT->create(lower, mid, init); L = LT;
    auto RT = new segtree; RT->create(mid+1, upper, init); R = RT;
}

void segtree::update(int pos, int new_val){
    if(pos<left||pos>right) return;
    if(left==right){val = max(val, new_val); return;}
    L->update(pos, new_val); R->update(pos, new_val);
    val = max(L->val, R->val);
}

int segtree::query(int start, int end){
    if(start<=left&&end>=right) return val;
    if(start>right||end<left) return 0;
    return max(L->query(start, end), R->query(start, end));
}

void segtree::wipe(){
    if(L!=nullptr) L->wipe(); if(R!=nullptr) R->wipe(); delete this;
}

int LIS_length(){
    sorted = seq; sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    order.resize(size, 0);
    for(int i=0; i<size; ++i) order[i] = lower_bound(sorted.begin(), sorted.end(), seq[i])-sorted.begin();
    auto RT = new segtree;
    RT->create(0, size-1);
    for(auto &i: order){
        RT->update(i, RT->query(0, i-1)+1);
    }
    int answer = RT->val;
    RT->wipe();
    return answer;
}

这两种解反映了 LIS 的本质是「一个序列中同时对两种偏序关系单调的子序列」，一个是下标/位置的偏序，一个是数值的偏序. 下标/位置的偏序关系我们在两个方法里都是通过时间的先后维持的：后加入线段树的节点下标大；数值的偏序关系体现在空间上，在贪心 version 中是通过一种压缩的形式储存的，在线段树 version 中是蕴含在线段树内部的.
另外，这两种方法快的一大原因是使用的动态规划比较聪明，在递推时花小成本维护了之前的整个答案结构，明显降低了非递归查询的复杂度.

Good，一些 retrospect 总会利于新问题的解决. 我们稍微认真地叙述一遍本问题吧.

给定一棵树 $T$ ，每点有一个权值. 求在 $T$ 中任意选一个起点和一个终点后，其间路径上点（含起止点）的权值序列的 LIS 的最大长度.

从一条链推广到一棵树后，基本算法应该是不变的，所以我们试着把上面两种快算法推广到这来.
Before we start，有个共同的事实是，遍历数据的方法要由平凡的线性改成树上的周游. 由于有递推结构，淘汰 BFS 选用 DFS.
改变遍历方法对应的是维持前述的下标/位置的偏序；维持数值的偏序就依赖于那种算法本身了.

方法一：贪心+二分查找
推广方法一的手段不难想：回溯.
求普通 LIS 的解中，每走到一个位置的逻辑是这样的： $更新\ approx → 走到节点的下一个位置$ （“更新”指二分查找位置并修改值的一次操作）.
这里，我们把逻辑改为： $更新\ approx → 走到节点所有邻点的位置 → 撤回更新$ . 即在周游当前节点的子节点后撤销自己对 $approx$ 造成的改动，原因很单纯，我们不想让不同分叉的数值互相干扰.
比如，如果 $9$ 号节点的更新是把 $approx$ 的第 $4$ 个位置的值从 $1000$ 改到 $300$ ，那递归完 $9$ 号的邻点后就把第 $4$ 个位置改回 $1000$ ，不留痕迹.
这样遍历完一整棵树的复杂度好像还是 $O(n \log n)$ 啊？不错，只可惜遍历一遍解决不了此题. 题目要求起止点任意，我们的一次遍历只能求出起点固定的情况，也就是说遍历要做 $n$ 遍......
可以做点优化：只选度为 $1$ 的点作为遍历起点，显然结果仍然正确. 只是这样补救不了复杂度，最差情况下有 $n-1$ 个节点的度数都是 $1$ ，还得重复 $O(n)$ 次.
我们最终搞出了 $O(n^2 \log n)$ 的时间复杂度，空间复杂度则是 $O(n)$ .
参考代码：

#include <bits/stdc++.h>
 
#define TYPE int
#define MAXN 200007
#define IOS_SPEED std::ios::sync_with_stdio(false)
 
using std::cin, std::cout;
using std::array, std::vector;
using std::lower_bound, std::max;
 
int size;
array<TYPE, MAXN> seq;
array<vector<int>, MAXN> next; // 原树每个节点的邻点集
array<bool, MAXN> visited;
vector<TYPE> LIS_approx;
int max_LIS_size = 1;
 
void travel(int cur){
    if(visited[cur]) return; visited[cur] = true;
    if(LIS_approx.empty()||seq[cur]>LIS_approx.back()){ // approx 所有元素小于当前值
        LIS_approx.push_back(seq[cur]); // update: 在 approx 结尾添加当前值
        max_LIS_size = max(max_LIS_size, (int)LIS_approx.size()); // 更新答案
        for(auto &neib: next[cur]) travel(neib); // 递归邻点
        LIS_approx.pop_back(); // 撤销 update
    }
    else{
        auto it = lower_bound(LIS_approx.begin(), LIS_approx.end(), seq[cur]); // 第一个值 ≥ 当前值的位置
        TYPE now_it = *it; // 临时记录该位置原先值
        *it = seq[cur]; // update: 改值
        for(auto &neib: next[cur]) travel(neib); // 递归邻点
        it = lower_bound(LIS_approx.begin(), LIS_approx.end(), seq[cur]); // 重新找到原位置; 不能用之前的迭代器 it, 因为 std::vector 加元素会 reallocate 使迭代器失效
        *it = now_it; // 撤销 update
    }
}
 
void prefix_LIS_builder(){
    for(int i=1; i<=size; i++){
        if(next[i].size()==1){ // 只选度为 1 的点作起点
            visited.fill(false);
            LIS_approx.clear();
            travel(i);
        }
    }
}
 
void interface(){
    IOS_SPEED; cin >> size;
    seq.fill(0);
    for(int i=1; i<=size; i++) cin >> seq[i];
    next.fill({}); int X, Y;
    for(int i=1; i<size; i++){
        cin >> X >> Y;
        next[X].push_back(Y); next[Y].push_back(X);
    }
    prefix_LIS_builder();
    cout << max_LIS_size << "\n";
    LIS_approx.clear();
}
 
int main()
{
    interface();
    return 0;
}

复杂度不低，但是对 Codeforces 490F 的小数据可以通过 (717 ms).

方法二：线段树
方法一必须遍历树 $O(n)$ 遍的原因是算法本身的压缩存储太巧，可推广性差. 虽然动规时是遍历了树，但严格朝着遍历的方向，不能顺便记录其它方向的答案结构.
而线段树可以做到这种工作，从而只需要一次遍历.
拿一个例子分析下我们的需求. 假如现在遍历到树的一个“分叉点”（度数大于 $2$ 的点），权值为 $7$ ，其有两个分叉是两条链，假设从分叉点看去两分叉的点权序列分别是 $11-12-4-3$ 和 $5-9-1$ . 所要的最长 LIS 可能产生在多种地方，包括：
A. 不带 $7$ ，从分叉一的结尾开始到分叉二的结尾结束： $3-4-5-9$ 等；
B. 不带 $7$ ，从分叉二的结尾开始到分叉一的结尾结束： $1-9-11-12$ 等；
C. 带上 $7$ ，从分叉一的结尾开始到分叉二的结尾结束： $3-4-7-9$ 等；
D. 带上 $7$ ，从分叉二的结尾开始到分叉一的结尾结束： $1-5-7-11-12$ 等.

这些情况必须都被列举出来. 怎么做到呢？有几件事是能做的：

在每个节点要将几个分叉的信息融合，所以 DFS 顺序最好是后根周游.
节点信息不仅要有「此点以后沿此方向所有的 LIS 信息」，还要有「此点以后沿此方向所有的最长下降子序列（LDS）信息」，而且两个值无关，应该分开存.
每个分叉/邻点的信息存于线段树内，所以为了综合所有分叉的信息，需设计线段树的融合操作.
遍历节点更新最大长度时，需要讨论是否包括该节点的两种情况. 每种情况都要尝试将分叉的 LIS/LDS 相接得出当前最优长度.

2：存 LDS 信息并不难，把 LIS 的更新逻辑 $update(i, query(0, i-1)+1)$ 修改成 $update(i, query(i+1, n-1)+1)$ 即可.
3：现在来设计线段树的融合. 首先，所有邻点的线段树融合可以简化为两两融合. 融合的本质是把两棵线段树的信息合并到一棵新树内.
然后看融合两棵线段树的方法，我们的思路是从两棵树的根出发，各自 DFS，更新每点的值. 容易想到，更新的逻辑是取最大.
但存在一个问题，完整 DFS 两棵树的成本是 $O(n)$ ，承担不起. 这时有两个优化手段：第一，两棵树在这个问题里往往没有多少公共的非空节点（“非空”指节点权值非 $0$ ，即对应的数值被访问过；如上面 $3-4-12-11$ 和 $5-9-1$ 两个分叉线段树的最后一层无公共非空节点），这时根本不必 DFS 两棵树，只用把一棵树的非空节点/子树接到另一棵树的空位置，而若都为空节点就跳过；第二，空节点没必要真的创建出来，动态创点并用 nullptr 标记空能节省大量时间和空间.
线段树融合的复杂度最差为 $O(n)$ ，最好为 $O(1)$ . 平均复杂度就复杂了，我并不会算，据说是 $O(\log n)$ ，姑采信之.
4：两种情况的讨论需要两种更新答案的操作.
情形一：包括当前节点. 这时只用查找所有分叉里，开头值大于该节点权值的最长 LIS 和开头值小于该节点权值的最长 LDS，长度相加再加 $1$ （当然这两个 LIS 和 LDS 不能位于同一分叉；因此和实际做法略有不同，但精神一致）.
情形二：不包括当前节点. 则相接涉及到几个分叉内部元素的比较，这可在线段树融合这一步进行：线段树的一个节点表示一个（数值大小的）区间；DFS 两棵线段树时，访问的节点是对应的，因此每次都在访问两个分叉的同一数值区间. 每次到一个节点 $i$ 时就计算 $x=A\ 树\ i\ 左子节点的\ LIS\ 答案加上\ B\ 树\ i\ 右子节点的\ LDS\ 答案$ ，以及 $y=A\ 树\ i\ 右子节点的\ LDS\ 答案加上\ B\ 树\ i\ 左子节点的\ LIS\ 答案$ ，用 $x,y$ 更新最大值. 左右不同则取值区间不交，保证了相接位置的单调关系仍然成立.

解释复杂数据结构果然要花很多字，比较可意会不可言传......但拿一个例子演示能发现上面的每一步考虑都不复杂.
假设前述的融合复杂度正确，那么这个算法的时间复杂度为 $O(n \log n)$ ，空间复杂度为 $O(n)$ .
参考代码：

#include <bits/stdc++.h>

#define IOS_SPEED std::ios::sync_with_stdio(false)

using std::cin, std::cout;
using std::pair, std::make_pair;
using std::vector, std::deque;
using std::lower_bound, std::unique, std::sort, std::max;

int size;
vector<int> seq, sorted;
vector<int> order;
vector<vector<int>> next; // 原树每个节点的邻点集
deque<bool> visited;
int answer = 0;

class segtree{
    public:
        int left, right; // 区间左右端点
        int val_LIS, val_LDS; // 区间的 LIS 答案和 LDS 答案
        segtree *L, *R;
        segtree(int l = 0, int r = size-1): left(l), right(r), val_LIS(0), val_LDS(0), L(nullptr), R(nullptr){}
        inline int get_L_LIS(){if(L==nullptr) return 0; return L->val_LIS;} // 获取左树 LIS 答案
        inline int get_R_LDS(){if(R==nullptr) return 0; return R->val_LDS;} // 获取右树 LDS 答案
        void update(int pos, int new_val_LIS, int new_val_LDS); // 更新线段树叶节点值, 在此过程中动态创点
        pair<int, int> query(int start, int end); // 查询线段树内区间答案
        void blend(segtree *RHS); // 融合两棵线段树 this 和 RHS, 答案写入 this
        void wipe(); // 删除线段树
};

void segtree::update(int pos, int new_val_LIS, int new_val_LDS){
    if(pos<left||pos>right) return;
    val_LIS = max(val_LIS, new_val_LIS); val_LDS = max(val_LDS, new_val_LDS); // 更新答案
    if(left==right) return;
    int mid = (left+right)>>1;
    if(L==nullptr){auto LT = new segtree(left, mid); L = LT;} // 动态创点
    L->update(pos, new_val_LIS, new_val_LDS); // 更新左树
    if(R==nullptr){auto RT = new segtree(mid+1, right); R = RT;} // 动态创点
    R->update(pos, new_val_LIS, new_val_LDS); // 更新右树
}

pair<int, int> segtree::query(int start, int end){
    if(start<=left&&end>=right) return {val_LIS, val_LDS};
    if(start>right||end<left) return {0, 0};
    auto queryL = (L!=nullptr)? L->query(start, end): make_pair(0, 0); // 查询左树, 如为空返回 {0, 0}
    auto queryR = (R!=nullptr)? R->query(start, end): make_pair(0, 0); // 查询右树, 如为空返回 {0, 0}
    return {max(queryL.first, queryR.first), max(queryL.second, queryR.second)};
}

void segtree::blend(segtree *RHS){
    val_LIS = max(val_LIS, RHS->val_LIS); val_LDS = max(val_LDS, RHS->val_LDS); // 更新答案
    answer = max(answer, get_L_LIS()+RHS->get_R_LDS()); // 更新情形二的答案
    answer = max(answer, get_R_LDS()+RHS->get_L_LIS()); // 更新情形二的答案
    if(L==nullptr) L = RHS->L; // 如 this->L 为空, 将 RHS->L 接过来
    else if(RHS->L!=nullptr) L->blend(RHS->L); // this->L 不为空, 与 RHS->L 融合
    if(R==nullptr) R = RHS->R; // 如 this->R 为空, 将 RHS->R 接过来
    else if(RHS->R!=nullptr) R->blend(RHS->R); // this->R 不为空, 与 RHS->R 融合
    delete RHS; // 删除 RHS 的当前节点
}

void segtree::wipe(){
    if(L!=nullptr) L->wipe(); if(R!=nullptr) R->wipe(); delete this;
}

segtree* travel(int cur){ // 遍历原树的函数, 返回一棵线段树, 便于二树融合操作
    visited[cur] = true;
    auto RT = new segtree; // 创建本节点的线段树
    int max_LIS_before = 0, max_LDS_before = 0; // 用于更新情形一的答案, 表示以 cur 值为分界, 所有分叉中最长的 LIS 和 LDS
    for(auto &neib: next[cur]){ // 遍历分叉/邻点
        if(visited[neib]) continue;
        auto N_RT = travel(neib); // 得到当前分叉返回的线段树
        int this_LIS = N_RT->query(0, order[cur]-1).first; // 查当前分叉的“值小于 cur 值的 LIS 长”
        int this_LDS = N_RT->query(order[cur]+1, size-1).second;  // 查当前分叉的“值大于 cur 值的 LDS 长”
        answer = max(answer, max_LIS_before+this_LDS+1); // 更新情形一的答案
        answer = max(answer, max_LDS_before+this_LIS+1); // 更新情形一的答案
        max_LIS_before = max(max_LIS_before, this_LIS); // 更新“所有分叉中最长的 LIS”
        max_LDS_before = max(max_LDS_before, this_LDS); // 更新“所有分叉中最长的 LDS”
        RT->blend(N_RT); // 融合 RT 和当前分叉的线段树, 并更新情形二的答案
    }
    RT->update(order[cur], max_LIS_before+1, max_LDS_before+1); // 更新 RT 中 cur 对应叶节点的两个数值
    return RT;
}

void find_LIS_length(){ // 计算本题答案的函数
    sorted = seq; sort(sorted.begin(), sorted.end());
    sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
    order.resize(size, 0);
    for(int i=0; i<size; ++i) order[i] = lower_bound(sorted.begin(), sorted.end(), seq[i])-sorted.begin();
    visited.resize(size, false);
    auto RT = travel(0);
    RT->wipe();
}

void interface(){ // IO 接口
    IOS_SPEED;
    cin >> size;
    for(int i=0, new_val; i<size; ++i){cin >> new_val; seq.push_back(new_val);}
    next.resize(size);
    for(int i=1, X, Y; i<size; ++i){
        cin >> X >> Y;
        next[X-1].push_back(Y-1); next[Y-1].push_back(X-1);
    }
    find_LIS_length();
    cout << answer << "\n";
    seq.clear(); sorted.clear(); order.clear(); next.clear(); visited.clear();
}

int main()
{
    interface();
    return 0;
}

这样就可以通过 $n=200000$ 的数据了.

由此可见，线段树的做法虽然代码难度较高，但是推广性强.

本文完.

[OpenJudge 12444] List〔LIS、线段树、树上的DP〕

[OpenJudge 12444] List〔LIS、线段树、树上的DP〕

题目

思路

相关阅读更多精彩内容

友情链接更多精彩内容