2021牛客暑期多校训练营7 F、xay loves trees

题目大意

给出棵以为根的树，你要在第一棵树上选择若干个点，并且在第二棵树上选择相同编号的点。

现在要求你在第一棵树上选择的点，把他们连接的边全部找出来必须构成一条链；

并且你在第二棵树上选择的点，不能存在任何两个点他们之间有祖先关系，换句话说就是某个点选了，它全部的子树节点都不能选了。

现在要你输出合理的点集最大的点数。

Solution

考点：时间戳+线段树

我们对第二棵树，打上时间戳，这样我就知道了每个节点他的全部子树在区间的什么范围内，时间戳它可以用这里面若干个子区间，并且时间戳可以让同一个节点的不同子树在完全不相交的区间里面，并且会包含它全部的子树区间。

接着我再去第一棵树上进行。

我就假设就是那条链的底部，那么它头顶上最近的产生冲突的点就是我现在能选择的最大答案。

接下来就要去找如何找到它头顶上最近的产生冲突的点，那对应到深度就是最大深度的冲突点在哪里。

考虑线段树维护，我们每次查询区间这个区间内第一棵树里面深度最大的点是什么？

每次区间更新里面区间取为，即更新写法为。

如果是直接这样写的更新，那么这个点退出的时候就很难回到之前的状态了，所以我们就要用一个保存一下之前的值，这样我们在退出的时候只需要把当前区间内最后的一个深度掉就行。

又因为的特殊性，我们能保证里面的深度值是递增的，如果这个区间不为空的话，我们就让，这样我就可以保证在退出的时候一定可以回到之前的最大值。接下来再用左右区间的最大值更新一下是选子区间还是当前的深度。

最后注意我们区间是，线段树要开。

时间复杂度为。

const int N = 3e5 + 7;

struct Node {
#define mid (l + r >> 1)
#define ls rt << 1
#define rs rt << 1 | 1
#define lson ls,l,mid
#define rson rs,mid+1,r

    int maxi[N << 3];
    vector<int> a[N << 3];
    void push_up(int rt, int l, int r) {
        maxi[rt] = 0;
        if (a[rt].size())    maxi[rt] = a[rt].back();
        if (l != r)
            maxi[rt] = max({ maxi[rt],maxi[ls],maxi[rs] });
    }
    void build(int rt, int l, int r) {
        if (l == r) {
            maxi[rt] = 0;
            a[rt].clear();
            return;
        }
        build(lson);
        build(rson);
    }
    void update(int rt, int l, int r, int L, int R, int v) {
        if (L <= l && r <= R) {
            if (v != -1)    a[rt].push_back(v);
            else a[rt].pop_back();
            push_up(rt, l, r);
            return;
        }
        if (R <= mid)    update(lson, L, R, v);
        else if (L > mid)    update(rson, L, R, v);
        else {
            update(lson, L, mid, v);
            update(rson, mid + 1, R, v);
        }
        push_up(rt, l, r);
    }
    int query(int rt, int l, int r, int L, int R) {
        if (L <= l && r <= R)    return maxi[rt];
        int res = 0;
        if (a[rt].size())    res = a[rt].back();
        if (R <= mid)    res = max(res, query(lson, L, R));
        else if (L > mid)    res = max(res, query(rson, L, R));
        else {
            res = max(res, query(lson, L, mid));
            res = max(res, query(rson, mid + 1, R));
        }
        return res;
    }
#undef mid
#undef ls
#undef rs
#undef lson
#undef rson
}A;

int n;
vector<int> G1[N], G2[N];

int tot, dfnl[N], dfnr[N];

void dfsTree2(int u, int fa) {
    dfnl[u] = ++tot;
    for (auto& v : G2[u]) {
        if (v == fa)    continue;
        dfsTree2(v, u);
    }
    dfnr[u] = ++tot;
}

int dep[N], res;

void dfsTree1(int u, int fa, int pre_dep) {
    dep[u] = dep[fa] + 1;

    pre_dep = max(pre_dep, A.query(1, 1, tot, dfnl[u], dfnr[u]));
    res = max(res, dep[u] - pre_dep);

    A.update(1, 1, tot, dfnl[u], dfnr[u], dep[u]);
    for (auto& v : G1[u]) {
        if (v == fa)    continue;
        dfsTree1(v, u, pre_dep);
    }
    A.update(1, 1, tot, dfnl[u], dfnr[u], -1);
}

int solve() {
    n = read();

    tot = 0;
    for (int i = 1; i <= n; ++i) {
        G1[i].clear();
        G2[i].clear();
    }

    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G1[u].push_back(v);
        G1[v].push_back(u);
    }
    for (int i = 1; i < n; ++i) {
        int u = read(), v = read();
        G2[u].push_back(v);
        G2[v].push_back(u);
    }

    dfsTree2(1, 0);
    A.build(1, 1, tot);
    res = 1;
    dfsTree1(1, 0, 0);
    print(res);

    return 1;
}