bzoj 5186: [Usaco2018 Jan]Cow at Large

.

题意：给出一棵树，牛从某个点出发，农夫从叶子出发来抓住牛。问对于牛的每个出发点，最少需要几个农夫。
题解：点分治
设点$x$到最近的叶子节点的距离为$L(x)$。首先，走回头路肯定是不优的，所以农夫只会往根走，牛只会往叶子走。又因为两者速度相等，所以只会相遇，不会追上。那么相遇的地方x只要满足农民比牛到得早就可以了，即$L(x)≤depth(x)$。这些点构成了一棵棵子树，而每棵子树只需要一个农夫。所以我们可以把这些点赋一个权值$2−degree(x)$，一棵子树的权值和就是$1$。直接搞显然过不去，我们可以点分治一下。设$d(x)$为分支中心到$x$的距离。两个不同子树里的点$x,y$的距离就是$d(x)+d(y)$。所以当$y$作为出发点时，对答案产生贡献的点$x$就要满足$L(x)≤d(x)+d(y) \\\ L(x)−d(x)≤d(y)$开一个s数组，s[L(x) - d(x)] += 2 - degree(x)，然后取个前缀和，s[y]就表示了会对$y$产生的贡献和。注意要减去$x,y$在同一颗子树里的情况。求$L$的话随便DP一下就好了。

点分打错T到飞起，L也求错了。。我真菜qwq
代码：

#include <bits/stdc++.h>
using namespace std;

int n, sz[70010], root, num = 0, fst[70010];
struct edge
{
    int x, y, n;
} e[140010];
struct pnt
{
    // int deg = 0, L = 2147483647, ans = 0;
    int deg, L, ans;
    bool v;
    pnt()
    {
        deg = ans = v = 0;
        L = 2147483647;
    }
} p[70010];
struct table
{
    int S[140010], mn, mx, zero;
    bool got;
    table()
    {
        zero = got = mn = mx = 0;
        memset(S, 0, sizeof(S));
    }
    void clear()
    {
        memset(S + mn + 70005, 0, sizeof(int) * (mx - mn + 1));
        mn = mx = got = 0;
    }
    int &operator[](int x)
    { /*
        assert(x + 70005 >= 0 && x + 70005 < 140010);
        if (x + 70005 < 0 || x + 70005 > 140010)
        {
            printf("%d\n", x);
            assert(0);
        }*/
        if (!got)
        {
            mn = min(mn, x);
            mx = max(mx, x);
        }
        if (x < mn)
            return zero;
        else if (x > mx)
            return S[70005 + mx];
        else
            return S[70005 + x];
    }
    void gsum()
    {
        got = 1;
        int l = mn + 1 + 70005, r = mx + 70005;
        for (int i = l; i <= r; i++)
            S[i] += S[i - 1];
    }
} s1, s2;

void getL1(int x, int fa)
{
    if (p[x].deg == 1)
    {
        p[x].L = 0;
    }
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y == fa)
            continue;
        getL1(y, x);
        p[x].L = min(p[x].L, p[y].L + 1);
    }
}
void getL2(int x, int fa)
{
    if (fa)
        p[x].L = min(p[x].L, p[fa].L + 1);
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y == fa)
            continue;
        getL2(y, x);
    }
}
void getsz(int x, int fa)
{
    sz[x] = 1;
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (p[y].v || y == fa)
            continue;
        getsz(y, x);
        sz[x] += sz[y];
    }
}
int gr(int x, int fa, int full)
{
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y != fa && !p[y].v && (sz[y] << 1) >= full)
            return gr(y, x, full);
    }
    return x;
}
void getroot(int x, int fa)
{
    getsz(x, fa);
    root = gr(x, fa, sz[x]);
}
void dfs(table &s, int x, int fa, int dep)
{
    // printf("%d\n", x);
    s[p[x].L - dep] += 2 - p[x].deg;
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y == fa || p[y].v)
            continue;
        dfs(s, y, x, dep + 1);
    }
}
void update(table &s1, table &s2, int x, int fa, int dep)
{
    if (p[x].deg != 1)
        p[x].ans += s1[dep] - s2[dep];
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y == fa || p[y].v)
            continue;
        update(s1, s2, y, x, dep + 1);
    }
}
void wk(int x)
{
    // printf("s1:%d\n", x);
    s1.clear();
    dfs(s1, x, 0, 0);
    s1.gsum();
    if (p[x].L)
        p[x].ans += s1[0]; /*
    for (int i = s1.mn; i <= s1.mx; i++)
        printf("%d %d\n", i, s1[i]);*/
    p[x].v = 1;
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (p[y].v)
            continue;
        s2.clear();
        dfs(s2, y, x, 1);
        s2.gsum(); /*
        printf("s2:%d\n", y);
        for (int j = s2.mn; j <= s2.mx; j++)
            printf("%d %d\n", j, s2[j]);*/
        update(s1, s2, y, x, 1);
    }
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (p[y].v)
            continue;
        getroot(y, x);
        wk(root);
    }
}
void ins(int x, int y)
{
    e[++num] = {x, y, fst[x]};
    fst[x] = num;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ins(x, y);
        ins(y, x);
        p[x].deg++;
        p[y].deg++;
    }
    getL1(1, 0); /*
    for (int i = 1; i <= n; i++)
        printf("%d ", p[i].L);
    puts("");*/
    getL2(1, 0); /*
    for (int i = 1; i <= n; i++)
        printf("%d ", p[i].L);
    puts("");*/
    for (int i = 1; i <= n; i++)
        if (p[i].deg == 1)
            p[i].ans = 1;
    getroot(1, 0);
    int hh = root;
    wk(root);
    for (int i = 1; i <= n; i++)
        printf("%d\n", p[i].ans);
}