\(\mathscr{Description}\)

Link.

给定两棵含 \(n\) 个结点的树 \(T_1=(V_1,E_1),T_2=(V_2,E_2)\)，求一个双射 \(\varphi:V_1\rightarrow V_2\)，使得 \(\forall (u,v)\in V_1^2,~(u,v)\notin E_1\lor (\varphi(u),\varphi(v))\notin E_2\)，或声明无解。

\(n\le10^4\)。

\(\mathscr{Solution}\)

为方便叙述，若 \(T\) 中最大结点度数为 \(d\)，那么称 \(T\) 为 \((n-1-d)\)-star，即一个 \(k\)-star 可以通过删去 \(k\) 个点变成菊花图。（或许外国友人叫它 star？）

首先，当然是猜无解条件：显然一个充分条件是，若 \(T_1\) 或 \(T_2\) 是 \(0\)-star，则无解。受此启发，我们连带着考虑 \(1\)-star 是否有解 <motivation>。不妨设 \(T_1\) 是 \(k\)-star，\(T_2\) 是非 \(0\)-star 的任意树。直观感受，\(T_1\) 有一个限制极强的“花蕊”——在 \(\varphi\) 作用后它只能和一个结点连边，因此它必然被映到 \(T_2\) 的一片叶子上。此后的构造就很简单了，这里给出 tutorial 里的图（其中 \(w\) 即“花蕊”，\(\varphi(v)\) 是 \(\varphi(w)\) 唯一能连向的点）：

现在已经得到 \(1\)-star 的解，还是直观地想，比 \(1\)-star 限制弱的 \(2\)-star, \(3\)-star, … 是否都有解呢？我们可以尝试用归纳证明这一结论，一方面确认结论正确性，另一方面，归纳过程往往就展现了构造过程 <motivation>。

宽泛地讲，大致的归纳过程应是：在 \(V_1\) 和 \(V_2\) 中取出两个小点集 \(S_1,S_2\)，保证 \(V_1\setminus S_1\) 和 \(V_2\setminus S_2\) 各自的诱导子图不是 \(0\)-star，并且在得到两个诱导子图的构造后，一定能够找到合法的 \(S_1\rightarrow S_2\)。为了归纳的简洁，我们尽量让 \(V_1\setminus S_1\) 和 \(V_2\setminus S_2\) 的诱导子图是树，继而要求 \(S_1,S_2\) 是当前 \(T_1,T_2\) 的叶子集 <motivation>；此外，为了保证有解，取出两片与同一结点邻接的叶子就显得很冒险——如果一者不合法，另一者也不可能替换它的映射，这种坏事应该避免 <motivation>。最终，可以汇总得到这样一个 motivation: \(S_1,S_2\) 分别是 \(T_1,T_2\) 中两片不邻接与同一结点的，删去后不会构成 \(0\)-star 的叶子。

感性分析后，我们来理性证明。对于不是 \(0\)-star 或 \(1\)-star 的 \(T_1\) 与 \(T_2\)，尝试在其中分别取出满足上述要求的叶子 \(\{u_1,v_1\}\subseteq V_1\) 和 \(\{u_2,v_2\}\subseteq V_2\)，它们在各自树上的唯一临接点分别是 \(\{x_1,y_1\},\{x_2,y_2\}~(x_1\neq y_1,x_2\neq y_2)\)。对 \(V_1\setminus \{u_1,v_1\}\) 和 \(V_2\setminus\{u_2,v_2\}\) 进行归纳得到一个 \(\varphi\)。现考虑能否为 \(\varphi\) 定义 \(\{u_1,v_1\}\rightarrow\{u_2,v_2\}\)：

不妨令 \(\varphi(u_1):=u_2,\varphi(v_1):=v_2\)，若此时 \(\varphi\) 不合法，那么 \((u_2,\varphi(x_1))\in E_2\lor (v_2,\varphi(y_1))\in E_2\)，可见 \(\varphi(x_1)=x_2\lor\varphi(y_1)=y_2\)，结合 \(\varphi\) 是双射这个基本条件，可知 \((v_2,\varphi(x_1))\notin E_2\land (u_2,\varphi(y_1))\notin E_2\)，因此此时定义 \(\varphi(u_1):=v_2,\varphi(v_1):=u_2\) 一定合法。

没画框框的原因是第一步加粗的“尝试”，以 \(T_1\) 为例，我们真的能取出 \(\{u_1,v_1\}\) 吗？

不能！但是问题不大，可以说明当 \(T_1\) 不是 \(0\)-star 或 \(1\)-star 时，仅有 \(|V_1|=5\) 时有特例。鉴于这里是 OI 而非 MO <motivation>，我们可以大力讨论所有 \(|V_1|=|V_2|=5\) 并证明它们都有解，算法实现时大力全排列得到它们的解。综上，有原结论成立。 \(\square\)

经过精细实现可以做到 \(\mathcal O(n\log n)\)，由于担心有人 \(\mathcal O(n^2)\) 莽过了这里简单提一下。我们不选确定的根，而是动态维护最大度数的结点。对于每个结点，维护其当前与其邻接的叶子集 \(L_u\) 以及这棵树可用叶子集 \(L_T\)，保证仅选取 \(L_u\) 中的一个元素加入 \(L_T\)。这样，从 \(L_T\) 任取两个点，简单判一下删去它们是否构成 \(0\)-star，若可行，则更新它们临接点的 \(L\) 集合，若发现邻接点也成了叶子就再加入邻接点的邻接点的 \(L\) 集合即可。这 \(n\) 挺小的，全程 std::set 乱飞应该没什么问题√

\(\mathscr{Code}\)

/*+Rainybunny+*/

#include <bits/stdc++.h>

#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)

#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)

typedef std::pair<int, int> PII;

#define fi first

#define se second

const int MAXN = 1e4;

int n, deg[2][MAXN + 5], fa[2][MAXN + 5], ref[MAXN + 5];

// fa[t][u] is defined only when u is a leaf.

bool rsv[MAXN + 5];

std::set<PII> edge[2], mdeg[2];

std::set<int> lbuc[2];

std::vector<int> adj[2][MAXN + 5];

std::deque<int> ch[2][MAXN + 5];

inline bool exist(const int t, int u, int v) {

    if (u > v) u ^= v ^= u ^= v;

    return edge[t].count({ u, v });

}

inline void init(const int t, const int u, const int las) {

    if (las && deg[t][u] == 1) ch[t][fa[t][u] = las].push_front(u);

    for (int v: adj[t][u]) if (v != las) {

        if (!las && deg[t][u] == 1) ch[t][fa[t][u] = v].push_front(u);

        init(t, v, u);

    }

}

inline bool check(const int u) {

    for (int v: adj[0][u]) {

        if (ref[v] > 0 && exist(1, ref[u], ref[v])) {

            return false;

        }

    }

    return true;

}

inline void solve(const int rest) {

    int rt0 = mdeg[0].rbegin()->se, rt1 = mdeg[1].rbegin()->se;

    if (rest <= 5) { // detailed situation, brute force.

        int p[6] = {}, q[6] = {};

        rep (i, 1, n) {

            if (!ref[i]) p[++p[0]] = i;

            if (!rsv[i]) rsv[q[++q[0]] = i] = true;

        }

        do {

            bool flg = true;

            rep (i, 1, p[0]) ref[p[i]] = 0;

            rep (i, 1, p[0]) {

                ref[p[i]] = q[i];

                if (!(flg = check(p[i]))) break;

            }

            if (flg) return ;

        } while (std::next_permutation(q + 1, q + q[0] + 1));

        assert(false); // since there's a solution existing, it's impossible.

    } else if (deg[0][rt0] < rest - 2 && deg[1][rt1] < rest - 2) {

        // choose two pairs of leaves.

        assert(lbuc[0].size() >= 2 && lbuc[1].size() >= 2);

        int u0(*lbuc[0].begin()), v0(*++lbuc[0].begin());

        int u1(*lbuc[1].begin()), v1(*++lbuc[1].begin());

        if (deg[0][rt0] == rest - 3 && fa[0][u0] != rt0)

            v0 = ch[0][rt0].back();

        if (deg[1][rt1] == rest - 3 && fa[1][u1] != rt1)

            v1 = ch[1][rt1].back();

        auto update = [](const int t, const int u)->void {

            assert(u);

            lbuc[t].erase(ch[t][u].back());

            mdeg[t].erase({ deg[t][ch[t][u].back()]--, ch[t][u].back() });

            mdeg[t].erase({ deg[t][u]--, u });

            mdeg[t].insert({ deg[t][u], u });

            ch[t][u].pop_back();

            if (ch[t][u].size()) lbuc[t].insert(ch[t][u].back());

            if (deg[t][u] == 1) {

                for (int v: adj[t][u]) if (deg[t][v]) { fa[t][u] = v; break; }

                assert(fa[t][u]);

                ch[t][fa[t][u]].push_front(u);

                if (ch[t][fa[t][u]].size() == 1) lbuc[t].insert(u);

            }

        };

        update(0, fa[0][u0]), update(0, fa[0][v0]);

        update(1, fa[1][u1]), update(1, fa[1][v1]);

        ref[u0] = ref[v0] = -1, rsv[u1] = rsv[v1] = true;

        // printf("(%d,%d) & (%d,%d)\n", u0, v0, u1, v1);

        solve(rest - 2);

        ref[u0] = u1, ref[v0] = v1;

        if (!check(u0) || !check(v0)) ref[u0] = v1, ref[v0] = u1;

    } else if (deg[0][rt0] == rest - 2) { // rt0 is 1-star.

        // assert(lbuc[0].size() == 2);

        int x = *lbuc[0].begin(), y = *lbuc[1].begin();

        if (fa[0][x] == rt0) x = *lbuc[0].rbegin();

        rsv[ref[rt0] = y] = rsv[ref[x] = fa[1][y]] = true;

        int s = fa[0][x];

        rep (i, 1, n) if (!rsv[i]) {

            rsv[ref[s] = i] = true;

            if (check(s)) break;

            ref[s] = rsv[i] = false;

        }

        assert(ref[s]);

        for (int i = 1, j = 1; i <= n; ++i) if (!ref[i]) {

            while (rsv[j]) ++j;

            rsv[ref[i] = j++] = true;

        }

    } else { // rt1 is 1-star.

        // assert(lbuc[1].size() == 2);

        int x = *lbuc[1].begin(), y = *lbuc[0].begin();

        if (fa[1][x] == rt1) x = *lbuc[1].rbegin();

        rsv[ref[y] = rt1] = rsv[ref[fa[0][y]] = x] = true;

        int s = fa[1][x];

        rep (i, 1, n) if (!ref[i]) {

            rsv[ref[i] = s] = true;

            if (check(i)) break;

            ref[i] = rsv[s] = false;

        }

        assert(rsv[s]);

        for (int i = 1, j = 1; i <= n; ++i) if (!rsv[i]) {

            while (ref[j]) ++j;

            rsv[ref[j++] = i] = true;

        }

    }

}

int main() {

    scanf("%d", &n);

    rep (t, 0, 1) rep (i, 2, n) {

        int u, v; scanf("%d %d", &u, &v);

        if (u > v) u ^= v ^= u ^= v;

        u -= t * n, v -= t * n, ++deg[t][u], ++deg[t][v];

        edge[t].insert({ u, v });

        adj[t][u].push_back(v), adj[t][v].push_back(u);

    }

    rep (i, 1, n) {

        mdeg[0].insert({ deg[0][i], i });

        mdeg[1].insert({ deg[1][i], i });

        if (deg[0][i] == n - 1 || deg[1][i] == n - 1) return puts("No"), 0;

    }

    init(0, 1, 0), init(1, 1, 0);

    rep (t, 0, 1) rep (i, 1, n) {

        if (ch[t][i].size()) {

            lbuc[t].insert(ch[t][i].back());

        }

    }

    solve(n);

    puts("Yes");

    rep (i, 1, n) printf("%d%c", ref[i] + n, i < n ? ' ' : '\n');

    return 0;

}

巴特西

Solution -「CF 923F」Public Service

\(\mathscr{Description}\)

\(\mathscr{Solution}\)

\(\mathscr{Code}\)

最新文章

热门文章