自动搬运

查看原文

来自洛谷，原作者为

	DrBit Dedicatus545

搬运于2025-08-24 22:27:15，当前版本为作者最后更新于2021-02-26 00:10:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

蒟蒻的第一篇题解

首先看到这种类似“切两刀”的描述就很容易想到固定其中一刀的位置再利用某种手段快速地求出第二刀的位置。

一个显而易见的结论：假设三个块的大小分别为$a$,$b$,$c$且$a$的大小固定时，$b$和$c$越接近答案越优。

设$siz[x]$表示$x$的子树大小。

那么就有一个思路：枚举其中一个点$x$，$x$的父边作为第一刀的位置，在剩下的树中找一个节点$y$，使得$siz[y]$尽可能接近$\frac{N-siz[x]}{2}$，在dfs过程中把每个计算过的点的$siz$值扔进一个set里然后二分一下就好了。

但我们很快发现上面这个做法在$y$是$x$的祖先节点的时候会出问题，因为这个时候$y$的贡献不是$siz[y]$而是$siz[y]-siz[x]$。其实也很好处理，在dfs过程中把当前节点的祖先节点放进一个栈里，其余的节点放进另一个栈里。在计算放祖先节点的栈统一减一个$siz[x]$就好了

ps:multiset的s.erase(x)操作是清除所有权值等于x的元素，要是只想删一个可以采取s.erase(s.find(x))的写法

马蜂略丑，求轻喷/kel

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
using namespace std;
const int MAXN = 2e5 + 50;
const int INF = 0x3f3f3f3f;
multiset<int> s1, s2;
multiset<int>::iterator it;
int N, siz[MAXN], ans = INF;
struct edge
{
    int nxt, to;
} e[MAXN * 2];
int head[MAXN], edgetot;
int max(int a, int b, int c)
{
    return max(max(a, b), c);
}
int min(int a, int b, int c)
{
    return min(min(a, b), c);
}
void add(int x, int y)
{
    e[++edgetot].to = y;
    e[edgetot].nxt = head[x];
    head[x] = edgetot;
}
void pre(int x, int f)
{
    siz[x] = 1;
    for (int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == f)
            continue;
        pre(v, x);
        siz[x] += siz[v];
    }
}
void upd(int x, int y)
{
    // cout << x << " " << y << endl;
    int c = N - x - y;
    int maxn = max(x, y, c);
    int minn = min(x, y, c);
    ans = min(maxn - minn, ans);
}
void dfs(int x, int f)
{
    if (!s1.empty())
    {
        it = s1.lower_bound((N - siz[x]) / 2 + siz[x]);
        //因为祖先栈中的值比实际的贡献值大siz[x]
        //所以二分的基准值要加上siz[x]
        if (it != s1.end())
            upd(siz[x], *it - siz[x]);
        if (it != s1.begin())
        {
            it--;
            upd(siz[x], *it - siz[x]);
        }
    }
    if (!s2.empty())
    {
        it = s2.lower_bound((N - siz[x]) / 2);
        if (it != s2.end())
            upd(siz[x], *it);
        if (it != s2.begin())
        {
            it--;
            upd(siz[x], *it);
        }
    }
    if (x != 1)
        s1.insert(siz[x]);
    //节点入dfs栈时将权值加入祖先栈中
    for (int i = head[x]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == f)
            continue;
        dfs(v, x);
    }
    if (x != 1)
    {
        s1.erase(s1.find(siz[x]));
        s2.insert(siz[x]);
    }
    //节点出dfs栈时讲权值从祖先栈中移除加入另一个栈中
}
int main()
{
    scanf("%d", &N);
    for (int i = 1; i <= N - 1; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    pre(1, 0);
    dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}