练习树的各种性质 I

2025-07-16

思维

这不比斜优做着爽。

A - Tr/ee

https://atcoder.jp/contests/arc103/tasks/arc103_c

可以发现，类似删边的问题，删出来的连通块当中，靠下的是一个完整的子树；就可以转化为子树问题了。

容易想到枚举 \(i-1\) 时树的状态，尝试转化为 \(i\) 时的状态；进一步可以胡出来一堆方案（大概），这里我胡的是，初始设置一个单点，\(0\to 1\) 啥也不干，\(0\to 0\) 在当前根上再加一个叶子，\(1\to 0\) 新建一个带叶子的根并令其成为当前根的父亲，\(1\to 1\) 加一个父亲。

然后特判一下 \(s_1=0\) 和 \(s_n=1\) 和 \(s_i\ne s_{n-i}\) 的情况，发现其他时候都有解。

#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int n;
    std::string s;
    std::cin >> s, n = (int)s.length();
    s = "#" + s;
    if (s[1] == '0' || s[n] == '1') {
        std::cout << -1 << '\n';
        return 0;
    }
    for (int i = 1; i < n; ++i)
        if (s[i] != s[n - i]) {
            std::cout << -1 << '\n';
            return 0;
        }
    int tot = 1, rt = 1;
    for (int i = 2; i < n; ++i) {
        if (tot == i - 1) {
            if (s[i] == '0') {
                std::cout << rt << ' ' << ++tot << '\n';
                rt = tot;
                std::cout << rt << ' ' << ++tot << '\n';
            }
            else {
                std::cout << rt << ' ' << ++tot << '\n';
                rt = tot;
            }
        }
        else if (s[i] == '0')
            std::cout << rt << ' ' << ++tot << '\n';
    }
    if (tot != n)
        std::cout << rt << ' ' << n << '\n';
    return 0;
}

B - Keep Perfectly Matched

https://atcoder.jp/contests/arc183/tasks/arc183_d

发现这个『完美匹配』就是在树上给每个点找相邻点配对，看看能不能配上；继而发现由于点的总数为偶，一个点有且仅能有一个 siz 为奇的子树（不然非法），再发现对于任意一个点，删掉的点对要么来自其同一个子树；要么一个来自其奇子树，另一个来自其偶子树。

发现要求最大化距离，又只能删叶子，所以需要最小化 LCA 深度；有没有办法让每次的 LCA 都是根呢？让重心成为根，并保证每次操作的两个点都不来自同一个儿子即可（显然这样是完全可能的）。

接着写了一发发现过不了样例，原因是发现在偶子树中会出现『一个中途的节点本来有一个奇儿子，删去偶子树中的一个叶子后非法』的情况。显然这样的节点是一个偶儿子。确保每个偶儿子的奇儿子先被删掉就可以解决问题。

对重心的每个儿子，提前规划其节点被删除的顺序即可。

#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int n;
    std::cin >> n;
    std::vector<std::vector<int> > g(n + 1);
    for (int i = 1, x, y; i < n; ++i) {
        std::cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
    }
    std::vector<int> siz(n + 1);
    int rt = 0;
    std::function<void(int, int)> DFS = [&](int x, int fa) {
        siz[x] = 1;
        bool flag = 1;
        for (auto i : g[x])
            if (i != fa) {
                DFS(i, x);
                siz[x] += siz[i];
                if (siz[i] > n / 2)
                    flag = 0;
            }
        if (flag && n - siz[x] <= n / 2)
            rt = x;
        return;
    };
    DFS(1, -1);
    std::vector<std::vector<int> > lf(n + 1);
    int f1 = -1;
    auto comp = [&](int i, int j) { return siz[i] < siz[j]; };
    std::priority_queue<int, std::vector<int>, decltype(comp)> f0(comp);
    siz.assign(n + 1, 0);
    for (auto t : g[rt]) {
        DFS = [&](int x, int fa) {
            siz[x] = 1;
            for (auto i : g[x])
                if (i != fa) {
                    DFS(i, x);
                    siz[x] += siz[i];
                }
            return;
        };
        DFS(t, rt);
        DFS = [&](int x, int fa) {
            if (siz[x] % 2 == 0) {
                for (auto i : g[x])
                    if (i != fa && siz[x] % 2 == 1)
                        DFS(i, x);
                for (auto i : g[x])
                    if (i != fa && siz[x] % 2 == 0)
                        DFS(i, x);
            }
            else
                for (auto i : g[x])
                    if (i != fa)
                        DFS(i, x);
            lf[t].push_back(x);
            return;
        };
        DFS(t, rt);
        if (siz[t] & 1)
            assert(f1 == -1), f1 = t;
        else
            f0.push(t);
        std::reverse(lf[t].begin(), lf[t].end());
    }
    fprintf(stderr, "rt = %d\n", rt);
    assert(~f1);
    for (int _ = n / 2; _--; ) {
        assert(~f1);
        if (!_ && f0.empty()) {
            std::cout << f1 << ' ' << rt << '\n';
            break;
        }
        assert(!f0.empty());
        int t = f0.top();
        f0.pop();
        assert(!lf[f1].empty());
        assert(!lf[t].empty());
        std::cout << lf[f1].back() << ' ' << lf[t].back() << '\n';
        lf[f1].pop_back(), --siz[f1];
        lf[t].pop_back(), --siz[t];
        if (siz[f1])
            f0.push(f1);
        f1 = t;
    }
    return 0;
}

C - Fiolki

https://www.luogu.com.cn/problem/P5578

难点在于判断每一步有哪些反应发生；显然一个反应只会在某一步发生。

发现将倒水的操作视为连边 \(b_i\to a_i\)，那么形成了森林，把每个反应丢到 LCA 处等待 check。

发现在 LCA 之外，两种试剂不可能相遇；故最后遍历一遍反应序列，维护每种药水当前数量，在每个点处 check 即可。

再发现如果每次加边都在父亲处 check 所有可能发生的反应，复杂度肯定是错的；故用倍增求出两个点在 LCA 下方的点作为『检查点』，当『检查点』被合并到其父亲时，就可以 check 一下检查点上面挂的所有询问。显然每个点上的询问只会被检查一次；复杂度线性。

加上倍增 LCA 的复杂度，就可以 \(O(n\log n)\) 地完成。

#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<int> > g(n + 1);
    std::vector<int> f(n + 1), deg(n + 1), now(n + 1);
    for (int i = 1; i <= n; ++i)
        std::cin >> now[i];
    std::iota(f.begin() + 1, f.end(), 1);
    std::function<int(int)> find = [&](int x) {
        return x == f[x] ? x : f[x] = find(f[x]);
    };
    auto merge = [&](int x, int y) {
        f[find(x)] = find(y);
        return;
    };
    std::vector<std::pair<int, int> > a(m + 1);
    for (int i = 1; i <= m; ++i) {
        auto &[x, y] = a[i];
        std::cin >> x >> y, ++deg[x];
        g[y].push_back(x), merge(x, y);
    }
    std::vector<int> dep(n + 1);
    std::vector<std::vector<int> > fa(n + 1, std::vector<int> (21));
    for (int i = 1; i <= n; ++i)
        if (!deg[i]) {
            std::function<void(int)> DFS = [&](int x) {
                for (auto i : g[x]) {
                    fa[i][0] = x;
                    for (int j = 1; j <= 20; ++j)
                        fa[i][j] = fa[fa[i][j - 1]][j - 1];
                    dep[i] = dep[x] + 1, DFS(i);
                }
                return;
            };
            dep[i] = 1, DFS(i);
        }
    std::vector<std::vector<std::pair<int, int> > > t(n + 1);
    for (int x, y; k--; ) {
        std::cin >> x >> y;
        if (find(x) == find(y)) {
            std::pair<int, int> p(x, y);
            if (dep[x] != dep[y]) {
                if (dep[x] < dep[y])
                    std::swap(x, y);
                for (int i = 20; ~i; --i)
                    if (dep[fa[x][i]] > dep[y])
                        x = fa[x][i];
                if (fa[x][0] == y) {
                    t[x].push_back(p);
                    // printf("add (%d, %d) to %d\n", p.first, p.second, x);
                    continue;
                }
                x = fa[x][0];
            }
            for (int i = 20; ~i; --i)
                if (fa[x][i] != fa[y][i])
                    x = fa[x][i], y = fa[y][i];
            t[x].push_back(p), t[y].push_back(p);
        }
    }
    std::iota(f.begin() + 1, f.end(), 1);
    auto res(0ll);
    for (int i = 1; i <= m; ++i) {
        auto [x, y] = a[i];
        merge(x, y);
        for (auto [p, q] : t[x])
            if (find(p) == find(x) && find(q) == find(x)) {
                int u = std::min(now[p], now[q]);
                res += 2 * u, now[p] -= u, now[q] -= u;
            }
    }
    std::cout << res << '\n';
    return 0;
}

D - Permutation Tree

https://atcoder.jp/contests/arc095/tasks/arc095_d

随便画图，会发现，如果按层数从小到大标号，一个点的儿子只有最多一个不是叶子。一言以蔽之：毛毛虫。

然后就可以判断可行性了（直径就是虫身）。接下来需要考虑最小化答案字典序的问题，发现对于一个点的儿子，必须是虫足在其左、虫身在其右且必须严格按照层数标号。

字典序是个偏贪心的东西，所以可以开始瞎搞：发现虫足越多，标号更小的父亲就会越靠后，所以依次比较用两端开头的情况，如果到了虫身的某一段，哪种的儿子更少就选谁，然后直接按最小来标号即可。

实际上由于只有两种方案，你也可以两边都试试（）

#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int n;
    std::cin >> n;
    std::vector<std::vector<int> > g(n + 1);
    for (int i = 1, x, y; i < n; ++i) {
        std::cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
    }
    std::vector<int> dep(n + 1);
    std::function<void(int, int)> DFS = [&](int x, int fa) {
        for (auto i : g[x])
            if (i != fa) {
                dep[i] = dep[x] + 1;
                DFS(i, x);
            }
        return;
    };
    dep[1] = 1, DFS(1, -1);
    int p = std::max_element(dep.begin() + 1, dep.end()) - dep.begin();
    bool flag = 0;
    std::vector<int> node, cnt(n + 1), siz(n + 1);
    DFS = [&](int x, int fa) {
        siz[x] = 1;
        for (auto i : g[x])
            if (i != fa) {
                DFS(i, x);
                siz[x] += siz[i], ++cnt[x];
            }
        if (siz[x] > 1) {
            node.push_back(0), --cnt[x];
            for (auto i : g[x]) {
                if (i != fa && siz[node.back()] > 1 && siz[i] > 1)
                    flag = 1;
                if (i != fa && siz[i] > siz[node.back()])
                    node.back() = i;
            }
        }
        return;
    };
    DFS(p, -1), node.push_back(p);
    if (flag) {
        std::cout << -1 << '\n';
        return 0;
    }
    for (int i = 0, j = (int)node.size() - 1; i <= j; ++i, --j)
        if (cnt[node[i]] > cnt[node[j]]) {
            std::reverse(node.begin(), node.end());
            break;
        }
        else if (cnt[node[i]] < cnt[node[j]])
            break;
    int now = 0;
    for (auto i : node) {
        int rt = ++now;
        for (; cnt[i]--; std::cout << ++now << ' ');
        std::cout << rt << ' ';
    }
    std::cout << '\n';
    return 0;
}

E - Isomorphism Freak

https://atcoder.jp/contests/agc024/tasks/agc024_d

~~像在数有多少种化学环境的 H 是可以说的吗~~

鉴于这个，高中化学选择性必修三，给我们打下的坚实基础，我们可以非常迅速地注意到答案就是半径长。

然后最少叶子，发现一眼瞪不出来，糟糕！没关系，观察样例输出，发现这些答案的因数都挺多，故猜测是若干个数乘起来的；然后再发现是每层最大儿子数的乘积。

枚举中间的边（仅当直径长度为偶时）、点（奇偶都行）作为对称轴 / 对称中心的情况取 min 即可（原因是要尽量取靠近中心的点），注意边两端算两个儿子数。

~~所以为啥 \(n\) 这么小~~

#include <bits/stdc++.h>
const long long inf = 1e18;
int main() {
#ifdef ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
    std::freopen(".in", "r", stdin);
    std::freopen(".out", "w", stdout);
#endif
    int n;
    std::cin >> n;
    std::vector<std::vector<int> > g(n + 1);
    for (int i = 1, x, y; i < n; ++i) {
        std::cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
    }
    std::vector<int> dep(n + 1);
    std::function<void(int, int)> DFS = [&](int x, int fa) {
        for (auto i : g[x])
        if (i != fa) {
            dep[i] = dep[x] + 1;
            DFS(i, x);
        }
        return;
    };
    dep[1] = 1, DFS(1, -1);
    int p = std::max_element(dep.begin() + 1, dep.end()) - dep.begin();
    dep[p] = 1, DFS(p, -1);
    int q = std::max_element(dep.begin() + 1, dep.end()) - dep.begin();
    std::cout << (dep[q] + 1) / 2 << ' ';
    std::vector<int> node;
    std::vector<std::pair<int, int> > edge;
    if (dep[q] & 1) {
        DFS = [&](int x, int fa) {
            for (auto i : g[x])
                if (i != fa)
                    DFS(i, x);
            if (dep[x] == (dep[q] + 1) / 2)
                node.push_back(x), edge.emplace_back(x, fa);
            if (dep[x] == (dep[q] + 1) / 2 + 1)
                edge.emplace_back(x, fa);
            return;
        };
        DFS(p, -1);
    }
    else {
        std::function<bool(int, int)> DFS = [&](int x, int fa) {
            if (x == q)
                return true;
            bool ret = false;
            for (auto i : g[x])
                if (i != fa)
                    ret |= DFS(i, x);
            if (ret && dep[x] == dep[q] / 2 + 1)
                edge.emplace_back(x, fa);
            return ret;
        };
        DFS(p, -1);
    }
    long long res = inf;
    for (auto [x, y] : edge) {
        std::vector<int> cnt(n + 1);
        std::function<void(int, int, int)> DFS = [&](int x, int fa, int dep) {
            int son = 0;
            for (auto i : g[x])
                if (i != fa)
                    ++son, DFS(i, x, dep + 1);
            cnt[dep] = std::max(cnt[dep], son);
            return;
        };
        DFS(x, y, 1), DFS(y, x, 1);
        auto now(2ll);
        for (int i = 1; i <= n && cnt[i]; ++i)
            now *= cnt[i];
        res = std::min(res, now);
    }
    for (auto rt : node) {
        std::vector<int> cnt(n + 1);
        std::function<void(int, int, int)> DFS = [&](int x, int fa, int dep) {
            int son = 0;
            for (auto i : g[x])
                if (i != fa)
                    ++son, DFS(i, x, dep + 1);
            cnt[dep] = std::max(cnt[dep], son);
            return;
        };
        DFS(rt, -1, 1);
        auto now(1ll);
        for (int i = 1; i <= n && cnt[i]; ++i)
            now *= cnt[i];
        res = std::min(res, now);
    }
    std::cout << res << '\n';
    return 0;
}

言论

练习树的各种性质 II

练习决策单调性