F. LIS on Tree 树上根路径LIS

2024-08-28 14:52
文章标签 路径 tree 树上 lis

本文主要是介绍F. LIS on Tree 树上根路径LIS,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1 关于lower_bound
// 12345 查4 应该放在4 。而不是5的位置。。所以不是uppper。
//如果1235 查4 。可以优化5 。
2 关于 ans[u] = max(j, ans[p]);
维护一个max 一定从(premax,cur)中选出来的。
3 关于 memset(st, 0x3f, sizeof st);
这个和st + 1, st + n + 1 。。我们二分选的区间有关。
全部初始化为inf 那么可以把序列维护成
类似 1 3 5 inf inf inf inf 这样的。。边界都是inf
这样 对于任何一个查询的a[u]我们都可以通用🔥st + 1, st + n + 1 这个范围
而不用自定义 st+1 ,st+len+1
附:感觉写代码要对自己诚实 要审视🦋任何一个自己不确定的语句!

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll __int128_t
#define ar array<int, 2>
#define arr array<int, 3>
int  n, m, k, inf = 1LL << 61, mod = 998244353;// 1e9+7;
const int N = 5e5 + 50;
int a[N];
vector<int>mp[N];
int ans[N], st[N];
void dfs(int u, int p) {int j = lower_bound(st + 1, st + n + 1, a[u]) - st;ans[u] = max(j, ans[p]);int pre = st[j];st[j] = a[u];for (int v : mp[u]) {if (v == p)continue;dfs(v, u);}st[j] = pre;
};
void solve() {cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];for (int i = 1; i < n; ++i) {int x, y;cin >> x >> y;mp[x].push_back(y);mp[y].push_back(x);}memset(st, 0x3f, sizeof st);dfs(1, 0);for (int i = 1; i <= n; ++i)cout << ans[i] << '\n';
};signed main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(15);
#ifdef DEBUGfreopen("../1.in", "r", stdin);
#endif//init_f();//init();//expr();// int T; cin >> T; while(T--)solve();return 0;
}

这篇关于F. LIS on Tree 树上根路径LIS的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1115076

相关文章

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶

图的最短路径算法——《啊哈!算法》

图的实现方式 邻接矩阵法 int[][] map;// 图的邻接矩阵存储法map = new int[5][5];map[0] = new int[] {0, 1, 2, 3, 4};map[1] = new int[] {1, 0, 2, 6, 4};map[2] = new int[] {2, 999, 0, 3, 999};map[3] = new int[] {3, 7

vcpkg子包路径批量获取

获取vcpkg 子包的路径,并拼接为set(CMAKE_PREFIX_PATH “拼接路径” ) import osdef find_directories_with_subdirs(root_dir):# 构建根目录下的 "packages" 文件夹路径root_packages_dir = os.path.join(root_dir, "packages")# 如果 "packages"

226 Invert Binary Tree

//226 Invert Binary Tree//算法思路:主要使用递归算法public class Solution {public TreeNode invertTree(TreeNode root) {//1 出口 空节点if (root==null)return null;//2 递归 调用自己TreeNode left = root.left;TreeNode right = ro

jmeter依赖jar包找不到类路径

这两天我在纠结这个问题,为啥我maven打包放在jmeter路径下后,jmeter的bean Shell 就是找不到这个类。纠结很久解开了。我记录下,留给后来的朋友。   Error invoking bsh method: eval Sourced file: inline evaluation of: ``import org.apache.jmeter.protocol.http.s

运行.bat文件,如何在Dos窗口里面得到该文件的路径

把java代码打包成.jar文件,编写一个.bat文件,执行该文件,编译.jar包;(.bat,.jar放在同一个文件夹下) 运行.bat文件,如何在Dos窗口里面得到该文件的路径,并运行.jar文件: echo 当前盘符:%~d0 echo 当前路径:%cd% echo 当前执行命令行:%0 echo 当前bat文件路径:%~dp0 echo 当前bat文件短路径:%~sdp0 nc