C题

求一颗树删去某个点后 形成的森林的最长上升子序列 最短, 输出最短的值

思路 : 点分治 + 线段树合并

首先解决第一个问题 如何求一颗树的最长上升子序列 ?

首先 最容易想到的就是 树上dp 先将树变成一颗有根树 (根随意)

对于 一颗以点 为根的树 ， 所有经过 的 最长上升子序列（并不一定要选择, 只是构成的数组经过）, 要么 为端点

要么 为 中间的某个点, 如下图表示两种情况

那么只要以每个点为根 都求出上图所示的两种情况的LIS， 取 即使答案

方法有很多，这里说一下比较常见的， 线段树合并

对于 每一个点， 都开两颗权值线段树, 其中 lis[i] 表示 最后一个值不超过 所能构成的最长上升子序列的最大长度(只能在以 为根的某一条链上, 也就是数组以x为结尾), 表示最后一个值 不低于 的最长下降子序列的最大长度

那么对于第一种情况就非常好考虑了
如果我已经知道了 的一个子树是 , 且点 的权值是
那么 与 x 所构成的最长上升子序列那就应该是 查询 和 取最大值

对于第二种情况稍微有点复杂
观察下图情况

容易发现 对于 两颗 不同的子树 如果我已经知道了 他们的权值线段树
那么答案并不是 直接 与 合并 因为 所表示的权值线段树顺序是相对的!
所以答案应该是

那么会 树形 dp 的 应该就知道该怎么做了
那么只剩下最后一个问题 知道了所有的儿子, 怎么获得 的权值线段树的情况?

容易发现 对于x 的权值线段树， 我只关心每一个权值 对应lis，lds 的最大值，而不关心它究竟是哪一条链过来的！ 也就是说合并的时候 每一颗子树之间相互独立！
所以可以通过 线段树合并两个子树每一个权值取 来快速获得 的权值线段树

这里有个不易察觉的坑点， 当合并两颗子树的时候， 可能会形成一些新的最长上升子序列（也就是不选择根 的）！此时需要在合并的时候把所有的情况都考虑出来， 具体写法可以看代码
树上线段树合并时间复杂度 是 的 因为每次合并只有两颗树共同存在的点 会继续往下
每次合并复杂度都是 , 很明显，这就是启发式合并的复杂度

第二个问题 如何解决删点模型

个人感觉比起第一个问题这个比较容易想到

考虑以某一个点为根的树中删去点的答案怎么求？
很明显只需要暴力枚举每个儿子， 然后通过第一个的方法求每一个儿子所在子树的最长上升子序列取即可
在上述过程中我们还可以获得 所对应的子树， 比方说是

关键:

如果发现 对应的子树 是 那么我想答案更优 一定不会删去 除去的其他子树上的点！！
这个很显然， 就不证明了

也就意味这 通过删去点, 我们就会排除很多不可能的子树！（只会留下一颗可能的子树）
那么很明显, 每次删去树的重心， 会排除最多的可能
所以可以套用点分治的模型去做 (其实个人感觉本质上并不是点分治， 只是套用了这个模型)
时间复杂度

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int maxn = 1e5 + 5;
struct Node {
    int to, nex;
}edge[maxn << 1];
int head[maxn], cnt;
void add(int l, int r) {
    edge[++cnt].nex = head[l];
    edge[head[l] = cnt].to = r;
}
int n, a[maxn];
int siz[maxn];
bool used[maxn];
// 点分治 基础函数 
//get_siz求子树大小 
void get_siz(int fa, int x) {
    siz[x] = 1;
    for (int i = head[x]; i; i = edge[i].nex) {
        int to = edge[i].to;
        if (to == fa) continue;
        if (used[to]) continue;
        get_siz(x, to); 
        siz[x] += siz[to];
    }
}
// get_t 求重心     allsum 表示子树总数, t表示 要求的重心， t_ans 表示当前重心所对应的大小 
void get_t(int fa, int x, int allsum, int &t, int &t_ans) {
    int max_ = 0;
    for (int i = head[x]; i; i = edge[i].nex) {
        int to = edge[i].to;
        if (to == fa) continue;
        if (used[to]) continue;
        get_t(x, to, allsum, t, t_ans);
        max_ = max(max_, siz[to]); 
    }
    max_ = max(max_, allsum - siz[x]);
    if (max_ < t_ans) {
        t = x, t_ans = max_;
    }
}
// 返回 u 的子树的重心(保证 u 没有被标记过 ) 
int find(int u) {
    get_siz(u, u);
    int t = u, t_ans = 1e9;
    get_t(u, u, siz[u], t, t_ans);
    return t; 
}
// 权值线段树部分 
int lis[maxn << 6], lds[maxn << 6];
int nex[maxn << 6][2], idx;
int root[maxn];
// 新开点函数，因为dfs函数会多次用到，所以要回收内存， 每次操作不能保证新开的点一定为空 
void newnode(int &now) {
    now = ++idx;
    lis[now] = lds[now] = nex[now][0] = nex[now][1] = 0;
} 
void add(int l, int r, int &now, int pos, int v, int *ls) {
    if (!now) newnode(now);
    if (l == r) return (void)(ls[now] = max(ls[now], v));
    int mid = l + r >> 1;
    if (mid >= pos) add(l, mid, nex[now][0], pos, v, ls);
    else add(mid + 1, r, nex[now][1], pos, v, ls);
    ls[now] = max(ls[nex[now][0]], ls[nex[now][1]]);
} 
int query(int l, int r, int now, int L, int R, int *ls) {
    if (l >= L && r <= R) return ls[now];
    if (!now || l >= r) return 0;
    int mid = l + r >> 1;
    int ans = 0;
    if (mid >= L) ans = query(l, mid, nex[now][0], L, R, ls);
    if (mid < R) ans = max(ans, query(mid + 1, r, nex[now][1], L, R, ls));
    return ans;
}
// 将 x 和 y 这两颗子树合并  返回合并过程中可能会发现的最大值 
int merge(int l, int r, int &x, int y) {
    if (!x || !y) {
        x |= y;
        return 0;
    }
    if (l == r) {
        lis[x] = max(lis[x], lis[y]);
        lds[x] = max(lds[x], lds[y]);
        return 0;
    }
    // 那么这个点 两棵树都有 就有可能会形成新的上升子序列 
    int v = max(lis[nex[x][0]] + lds[nex[y][1]], lis[nex[y][0]] + lds[nex[x][1]]); 
    int mid = l + r >> 1;
    v = max(v, merge(l, mid, nex[x][0], nex[y][0]));
    if (mid < r) 
    v = max(v, merge(mid + 1, r, nex[x][1], nex[y][1]));
    lis[x] = max(lis[nex[x][0]], lis[nex[x][1]]);
    lds[x] = max(lds[nex[x][0]], lds[nex[x][1]]);
    return v;
}
// 查询 x的子树的最长上升子序列 
int dfs(int fa, int x) {
    // 每次查找前先清空 
    root[x] = 0;
    int maxlis = 0, maxlds = 0, max_ = 0;
    for (int i = head[x]; i; i = edge[i].nex) {
        int to = edge[i].to;
        if (to == fa) continue;
        max_ = max(max_, dfs(x, to));
        int tolis = query(1, n, root[to], 1, a[x] - 1, lis);
        int tolds = query(1, n, root[to], a[x] + 1, n, lds);
        max_ = max(max_, maxlis + tolds + 1);
        max_ = max(max_, maxlds + tolis + 1);
        maxlis = max(maxlis, tolis);
        maxlds = max(maxlds, tolds);
        // 树上合并 
        max_ = max(max_, merge(1, n, root[x], root[to]));
    }
    add(1, n, root[x], a[x], maxlis + 1, lis);
    add(1, n, root[x], a[x], maxlds + 1, lds);
    return max_;
}

// 记录答案 
int answer = 1e9; 
// 点分治函数 
void calc(int u) {
    used[u] = true;
    // 记录 以 u 为断点时， 组成的森林的最大值， 以及最大值所在的子树 
    int max_ = 0, maxpos = 0;
    for (int i = head[u]; i; i = edge[i].nex) {
        int to = edge[i].to;
        idx = 0;
        int val = dfs(u, to);
        if (val > max_) {
            max_ = val;
            maxpos = to;
        }
    }
    answer = min(answer, max_);
    // 如果找不到 或者 这个点在之前已经找过，那就不会在有可能更新答案了 
    if (used[maxpos]) {
        return; 
    }
    // 如果能到这里 证明 max_ 一定不为 0 那么 find 一定不为空
    calc(find(maxpos)); 
}
int main() {
    scanf("%d", &n);
     for (int i = 1, l, r; i < n; ++i) {
         scanf("%d%d", &l, &r);
         add(l, r), add(r, l);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }
    calc(find(1));
    cout << answer << endl;
    return 0;
}