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;
}