专栏文章

题解：P7165 [COCI 2020/2021 #1] Papričice

jjackzhangcn2013
P7165题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miozy8nu
此快照首次捕获于
2025/12/03 03:54
3 个月前
此快照最后确认于
2025/12/03 03:54
3 个月前
查看原文

题目大意

有一棵树，割两条边，使分成的三部分最大与最小部分之差最小。

解法

如果暴力枚举割的两条边，那时间复杂度最优也只能到 O(n2)O(n^2)，无法通过此题。
于是我们可以想到先固定一条边，再确定剩下的一条边。
由于已经分了一部分了，我们肯定希望剩下两部分的差尽量小，假设现在已经分了的部分大小为 sizsiz，那最好的结果一定就是两部分的大小都是 n−siz2\frac{n-siz}{2}，使用二分查找找出最接近这个只的一部分就行了，还有一部分自然就确定了。
时间复杂度为 O(nlog⁡(n))O(n\log(n))，可以通过此题。

实现

先预处理出所有节点的子树大小。
假设割的一条边为 fau→ufa_u\to u。
可以发现令一条边割在 uu 的祖先节点上和其他节点上是不一样的，因为祖先节点的子树包括 uu，故分两部分讨论。

祖先节点

记录下所有 uu 的祖先节点的子树大小，二分查找其中最接近 n−sizu2+sizu\frac{n-siz_u}{2}+siz_u 的节点（因为祖先节点的子树包括 uu 的子树，所以要加上 sizusiz_u）。

其他节点

与祖先节点同理，但由于其他节点的子树并不包含 uu 的子树，于是不需要加上 sizusiz_u。
最后统计答案即可。

代码

CPP
#include <bits/stdc++.h>
#define int long long
const int N = 2e5 + 5;
const int Mod = 1e9 + 7;
using namespace std;
int n;
vector<int> g[N];
int siz[N];
void pre(int u, int fa)
{
    siz[u] = 1;
    for (int v : g[u])
    {
        if (v != fa)
        {
            pre(v, u);
            siz[u] += siz[v];
        }
    }
}
multiset<int> other, father;
int ans = 1e18 + 5;
inline void upd(int a, int b, int c)
{
    ans = min(ans, max({a, b, c}) - min({a, b, c}));
}
void dfs(int u, int fa) // 第一刀剪在 u 和 fa 上
{
    // 第二刀可能在父节点上
    if (!father.empty())
    {
        auto it = father.lower_bound((n - siz[u]) / 2 + siz[u]); // 父节点子节点包含 u，加上补偿
        if (it != father.end())
        {
            upd(siz[u], *it - siz[u], n - *it);
        }
        if (it != father.begin())
        {
            it--;
            upd(siz[u], *it - siz[u], n - *it);
        }
    }
    // 第二刀可能在其他子树上
    if (!other.empty())
    {
        auto it = other.lower_bound((n - siz[u]) / 2);
        if (it != other.end())
        {
            upd(siz[u], *it, n - *it - siz[u]);
        }
        if (it != other.begin())
        {
            it--;
            upd(siz[u], *it, n - *it - siz[u]);
        }
    }
    if (u > 1) // 1 没有父节点
    {
        father.insert(siz[u]);
    }
    for (int v : g[u])
    {
        if (v != fa)
        {
            dfs(v, u);
        }
    }
    if (u > 1)
    {
        father.erase(father.find(siz[u]));
        other.insert(siz[u]);
    }
}
signed main()
{
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    siz[1] = 1;
    pre(1, 0);
    dfs(1, 0);
    cout << ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...