P7165 [COCI2020-2021#1] Papričice (set)

· · 题解

蒟蒻的第一篇题解

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

一个显而易见的结论：假设三个块的大小分别为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;
}