2021牛客多校7 F xay loves trees

题目描述

https://ac.nowcoder.com/acm/contest/11258/F

简要题意：给定两棵大小均为 $n$ 的树，求一个最大的点集满足，这些点在第一棵树上构成一条深度递增的链，即满足所有点之间都存在祖宗关系，在第二棵树上任意两点不存在祖宗关系

$n\le 3\times 10^5$

Solution

我们考虑对于每个点求其作为链的最底端的答案，我们令 $h[u]$ 表示 $u$ 作为最底端时，深度最深的点满足在第二颗树上与 $u$ 存在祖先关系的点的深度

那么答案显然是 $max\lbrace dep[u]-h[u]\rbrace$

我们考虑如何求 $h$，注意到两个点 $u$ 和 $v$ 如果存在祖先关系，当且仅当 $u$ 的子树和 $v$ 的子树有交，那么我们在第一棵树上 $dfs$，然后每到一个点 $u$，我们就将线段树上 $in[u]$ 到 $out[u]$ 都与 $dep[u]$ 取 $max$，但是取 $max$ 并不能撤回，所以我们考虑直接用主席树

时间复杂度 $O(n\log n)$

#include <iostream>
#include <algorithm>
#define maxn 300010
#define INF 1000000000
using namespace std;

int n;

struct Edge {
    int to, next; 
} e[maxn * 2], E[maxn * 2]; int c1, head[maxn], c2, Head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

inline void add_Edge(int u, int v) {
    E[c2].to = v; E[c2].next = Head[u]; Head[u] = c2++;
}

#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct Zhuxi {
    int v, tag, ch[2];
} T[maxn * 40]; int rt[maxn], top;
inline void maintain(int i) { T[i].v = max(T[lc].v, T[rc].v); }

void update(int &i, int j, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ; 
    i = ++top; T[i] = T[j];
    if (L <= l && r <= R) return T[i].v = max(T[i].v, v), T[i].tag = max(T[i].tag, v), void();
    int m = l + r >> 1;
    update(lc, Lc, l, m, L, R, v); update(rc, Rc, m + 1, r, L, R, v);
    maintain(i); 
}

int query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].v;
    int m = l + r >> 1;
    return max({ T[i].tag, query(lc, l, m, L, R), query(rc, m + 1, r, L, R) });
}

int in[maxn], out[maxn], c3; 
void Dfs(int u, int fa) {
    in[u] = ++c3; 
    for (int i = Head[u]; ~i; i = E[i].next) {
        int v = E[i].to; if (v == fa) continue;
        Dfs(v, u); 
    } out[u] = c3;
}

int dep[maxn], ans;
void dfs(int u, int fa, int mx) {
    update(rt[u], rt[fa], 1, n, in[u], out[u], dep[u]);
    mx = max(mx, query(rt[fa], 1, n, in[u], out[u]));
    ans = max(ans, dep[u] - mx); 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dep[v] = dep[u] + 1; dfs(v, u, mx);
    }
}

void work() {
    cin >> n;
    fill(head + 1, head + n + 1, -1); fill(Head + 1, Head + n + 1, -1);
    c1 = c2 = c3 = ans = 0; 
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    }
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_Edge(x, y); add_Edge(y, x); 
    } Dfs(1, 0); dep[1] = 1; dfs(1, 0, 0); cout << ans << "\n";
    for (int i = 1; i <= top; ++i) T[i] = { 0, 0, 0, 0 }; top = 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}