已完成今日之树上 LIS 大学习
2025-12-20 03:00:25
发布于：广东
4阅读
0回复
0点赞
题目：CF490F
题意解析：给定一棵 个节点的树，每个节点都有一个点权 。求在这棵树所有的路径中点权的 LIS 的最大值。
首先考虑暴力解法。
我们可以枚举每一个节点作为根节点的所有路径 LIS 最大值。
具体做法就是枚举根节点，然后进行 DP， 表示当前 的子树以 为结尾的 LIS 最大值。
显然可以 合并信息，总时间复杂度是 。
此时有两种优化方法：
- 不从头开始 DP，在以 为根的基础上进行换根 DP，可以优化至 ，可以通过。
- 考虑用更快的方法合并信息。我们可以使用 dsu on tree 方式来实现。。
但是仅仅就是这样了吗？
注意到一条经过 的路径可以由两个 的两个子树的路径和 拼成。
所以我们可以求 的子树的 LIS 和 LDS 最大值，然后拼起来。
假设 表示 的所有儿子， 记录当前 的子树以 结尾的 LIS 最大值， 记录 LDS 最大值，则答案为 。
直接暴力合并、查询是 的，但是我们可以使用 dsu on tree 来优化至 或 。这里我的方法是 的线段树合并。
首先 单独处理 的情况，然后合并信息的时候更新所有的答案。
对于当前点 与 的区间 ，显然可以按照以下方式更新答案：
- 如果任何一颗树没有记录这颗区间的答案，直接返回。
- 否则令 ，将 与 更新至答案中。显然这在线段树中对应着节点的左右子树，可以 更新。
- 向下递归至区间 与 。
- 合并 的信息至 。
代码如下：
namespace cjdst{
template <typename T>
class Mergable_Map{
class node{
public:
T lis, lds;
T left, right;
node *lson, *rson;
node(){
lis = lds = left = right = 0;
lson = rson = 0;
}
node(T l, T r){
lis = lds = 0;
lson = rson = 0;
left = l, right = r;
}
}*root;
void push_up(node *cur){
cur -> lis = std::max(cur -> lson -> lis, cur -> rson -> lis);
cur -> lds = std::max(cur -> lson -> lds, cur -> rson -> lds);
}
void build_son(node *cur){
if(cur -> lson) return;
T l = cur -> left, r = cur -> right;
T mid = (l + r) >> 1;
cur -> lson = new node(l, mid);
cur -> rson = new node(mid + 1, r);
}
void _modify(node *u, T idx, T lis, T lds){
if(u -> left == u -> right){
u -> lis = std::max(u -> lis, lis);
u -> lds = std::max(u -> lds, lds);
return;
}
build_son(u);
if(u -> lson -> right >= idx) _modify(u -> lson, idx, lis, lds);
else _modify(u -> rson, idx, lis, lds);
push_up(u);
}
node *_merge(node *u, node *&v, T &ans){
if(!u) return v;
if(!v) return u;
if(u -> left == u -> right){
u -> lis = std::max(u -> lis, v -> lis);
u -> lds = std::max(u -> lds, v -> lds);
return u;
}
if(u -> lson && v -> lson){
ans = std::max(ans, std::max(u -> lson -> lis + v -> rson -> lds,
v -> lson -> lis + u -> rson -> lds));
}
u -> lson = _merge(u -> lson, v -> lson, ans);
u -> rson = _merge(u -> rson, v -> rson, ans);
if(u -> lson) push_up(u);
return u;
}
T _query_lis(node *u, T idx){
if(!u) return 0;
if(u -> left == u -> right) return u -> lis;
build_son(u);
if(u -> lson -> right >= idx) return _query_lis(u -> lson, idx);
return std::max(u -> lson -> lis, _query_lis(u -> rson, idx));
}
T _query_lds(node *u, T idx){
if(!u) return 0;
if(u -> left == u -> right) return u -> lds;
build_son(u);
if(u -> rson -> left <= idx) return _query_lds(u -> rson, idx);
return std::max(u -> rson -> lds, _query_lds(u -> lson, idx));
}
void _test(node *u){
if(!u) return;
if(u -> left == u -> right){
std::cout << u -> left << ' ' << u -> val << '\n';
return;
}
_test(u -> lson), _test(u -> rson);
}
public:
Mergable_Map(){}
Mergable_Map(T l, T r){
root = new node(l, r);
}
void modify(T idx, T lis, T lds){
_modify(root, idx, lis, lds);
}
T merge(Mergable_Map &v){
T ans = 0;
_merge(root, v.root, ans);
v = Mergable_Map(root -> left, root -> right);
return ans;
}
T query_lis(T idx){
if(idx < root -> left) return 0;
return _query_lis(root, idx);
}
T query_lds(T idx){
if(idx > root -> right) return 0;
return _query_lds(root, idx);
}
};
int dfs(int cur, int fa, int n, std::vector <int> &a, std::vector <std::vector <int>> &v,
std::vector <Mergable_Map <int>> &dp){
int ans = 0;
int mxlis = 0, mxlds = 0;
for(int i:v[cur]){
if(i == fa) continue;
ans = std::max(ans, dfs(i, cur, n, a, v, dp));
int curlis = dp[i].query_lis(a[cur] - 1);
int curlds = dp[i].query_lds(a[cur] + 1);
ans = std::max(ans, std::max(mxlis + curlds + 1, mxlds + curlis + 1));
mxlis = std::max(mxlis, curlis);
mxlds = std::max(mxlds, curlds);
ans = std::max(ans, dp[cur].merge(dp[i]));
}
dp[cur].modify(a[cur], mxlis + 1, mxlds + 1);
return ans;
}
void solve(){
int n;
std::cin >> n;
std::vector <int> a(n + 5, 0);
std::vector <std::vector <int>> v(n + 5);
for(int i = 1; i <= n; i++) std::cin >> a[i];
for(int i = 1; i < n; i++){
int x, y;
std::cin >> x >> y;
v[x].push_back(y), v[y].push_back(x);
}
std::vector <Mergable_Map <int>> dp(n + 5);
for(int i = 1; i <= n; i++){
dp[i] = Mergable_Map <int>(1, 1000000);
}
std::cout << dfs(1, 0, n, a, v, dp) << '\n';
}
}
没离散化，时间复杂度 。
由于贺了题解，代码有点诡异（（（
有帮助，赞一个