F - LIS on Tree
Problem Statement: here
Solution:
There is more than one way to solve this problem. We shall see two different implementations.
The first implementation is an easy version and it uses LIS in O(nlogn) approach. We will apply dfs from the root node and insert each element as if we do it in a linear array. But, the only difference is, once the subtree query is finished, replace the old version for the next subtree.
The second implementation involves using segment trees to answer the LIS in O(nlogn) approach. I will include this approach and its brief explanation as to my next post in the series on segment trees.
So, stay tuned with it!
To learn how to compute LIS in O(nlogn) check my this post
Using the Vector for LIS: AC in 121mS
V(ll) adj[200005];
ll n,k;
ll val[200005];
ll dp[200005];
V(ll) v; // declaring vector
void dfs(ll node, ll parent){
ll rep = -1;
auto it = lower_bound(all(v),val[node]);
ll ind = it - v.begin();
if (it != v.end()) {
rep = *it;
*it = val[node];
}
else v.PB(val[node]);
dp[node] = v.size();
for(ll child:adj[node]){
if (child != parent){
dfs(child,node);
}
}
if (rep != -1){
v[ind] = rep;
}
else{
v.pop_back();
}
}
void solve()
{
cin >> n;
rep(i,1,n+1) cin >> val[i];
rep(i,0,n-1){
ll x,y;
cin >> x >> y;
adj[x].PB(y);
adj[y].PB(x);
}
dfs(1,-1);
rep(i,1,n+1) cout << dp[i] << endl;
}
Using a Set for LIS: AC in 175mS
V(ll) adj[200005];
ll n,k;
ll val[200005];
ll dp[200005];
set<ll> s;
void dfs(ll node, ll parent){
ll rep = -1;
auto it = s.lower_bound(val[node]);
if (it != s.end()) {
rep = *it;
s.erase(it);
}
s.insert(val[node]);
dp[node] = s.size();
for(ll child:adj[node]){
if (child != parent){
dfs(child,node);
}
}
s.erase(val[node]);
if (rep != -1){
s.insert(rep);
}
}
void solve()
{
cin >> n;
rep(i,1,n+1) cin >> val[i];
rep(i,0,n-1){
ll x,y;
cin >> x >> y;
adj[x].PB(y);
adj[y].PB(x);
}
dfs(1,-1);
rep(i,1,n+1) cout << dp[i] << endl;
}
Using a multi set for LIS: AC in 186mS
V(ll) adj[200005];
ll n,k;
ll val[200005];
ll dp[200005];
multiset<ll> s;
void dfs(ll node, ll parent){
ll rep = -1;
auto it = s.lower_bound(val[node]);
if (it != s.end()) {
rep = *it;
s.erase(it);
}
s.insert(val[node]);
dp[node] = s.size();
for(ll child:adj[node]){
if (child != parent){
dfs(child,node);
}
}
s.erase(s.find(val[node]));
if (rep != -1){
s.insert(rep);
}
}
void solve()
{
cin >> n;
rep(i,1,n+1) cin >> val[i];
rep(i,0,n-1){
ll x,y;
cin >> x >> y;
adj[x].PB(y);
adj[y].PB(x);
}
dfs(1,-1);
rep(i,1,n+1) cout << dp[i] << endl;
}
Questions to look ahead?
- https://open.kattis.com/problems/neverjumpdown
- I will upload the solution to this soon.
- You can leave a comment if you find some exciting problems on LIS over trees
No comments:
Post a Comment