9.CF490F Treeland Tour 线段树合并

9.CF490F Treeland Tour 线段树合并

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

给出一棵带点权树，求树上最长上升子序列的长度

对每个点开两棵线段树，记录叶节点到当前节点的LIS和LDS，然后合并时取最大值即可

洛谷传送门：CF490F Treeland Tour - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：F. Treeland Tour (codeforces.com)

题目分析

给出一棵带点权树，求树上最长上升子序列的长度

对每个点开两棵线段树，记录叶节点到当前节点的LIS和LDS，然后合并时取最大值即可

可以假定 w u w_u wu​ 就为一段路径的中间必经点，现在就只需要在子树里找到一截尾部小于 w u w_u wu​ 的 L I S LIS LIS，和一截尾部大于 w u w_u wu​ 的 L D S LDS LDS，加起来再加一就行了。

设我们正在合并的两个线段树结点 x 1 , x 2 x_1, x_2 x1​,x2​，我们只考虑统计跨 m i d = l x + r x 2 mid=\frac {l_x+r_x} 2 mid=2lx​+rx​​的答案，那么显然只需在 [ l , m i d ] [l, mid] [l,mid] 中找出一条最长的 最长上升/下降子序列 与 [ m i d + 1 , r ] [mid+1, r] [mid+1,r]中找出的一条最长的 最长上升/下降子序列 拼在一起。这样找出的两条拼在一起一定是合法的，因为线段树的下标即为结尾元素的值。

代码实现细节比较多，容易写挂。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
// #define int long long
#define endl '\n'
using namespace std;

const int N = 6005, MOD = 1e9 + 7;
int w[N], b[N], n1, ans;

vector g[N];

void diz(int n){
    sort(b + 1, b + 1 + n);
    n1 = unique(b + 1, b + 1 + n) - (b + 1);
    for(int i = 1; i > 1;
        if(mid >= pos) update(lson, pos, val1, val2);
        else update(rson, pos, val1, val2);
        push_up(rt);
    }

    void query(int rt, int l, int r, int L, int R, int &nlis, int &nlds){
        if(!rt) return;
        if(l >= L && r > 1;
        if(mid >= L) query(lson, L, R, nlis, nlds);
        if(mid > 1;
        lis[u] = std::max(lis[u], lis[v]);
        lds[u] = std::max(lds[u], lds[v]);
        ans = std::max({ans, lis[lc[u]] + lds[rc[v]], lds[rc[u]] + lis[lc[v]]});
        lc[u] = merge(lc[u], lc[v], l, mid);
        rc[u] = merge(rc[u], rc[v], mid + 1, r);
        // push_up(u);
        return u;
    }
}

#define root SegTree::root
#define SEGRG root[i], 1, n1

void dfs(int u, int fa){
    int mlis = 0, mlds = 0;
    for(auto &v : g[u]){
        if(v == fa) continue;
        dfs(v, u);
        int vlis = 0, vlds = 0, tmp = 0;
        SegTree::query(root[v], 1, n1, 1, w[u] - 1, vlis, tmp);
        SegTree::query(root[v], 1, n1, w[u] + 1, n1, tmp, vlds);
        ans = max(ans, mlis + vlds + 1);
        ans = max(ans, mlds + vlis + 1);
        mlis = max(mlis, vlis), mlds = max(mlds, vlds);
        root[u] = SegTree::merge(root[u], root[v], 1, n1);
    }
    SegTree::update(root[u], 1, n1, w[u], mlis + 1, mlds + 1);
}

inline void solve(){
    int n = 0; cin >> n; ans = -1, SegTree::clear();
    for(int i = 1; i > w[i], b[i] = w[i];
    for(int i = 1; i > u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    diz(n);
    for(int i = 1; i