【提醒后人】线段树合并

Biuld @ 2023-10-12 07:53:17

by Saka_Noa @ 2023-10-12 08:05:34

#include <bits/stdc++.h>
using namespace std;
#define _ (int)(1e6 + 5)
#define lc ls[k]
#define rc rs[k]
#define lcon lc, l, mid
#define rcon rc, mid + 1, r
#define Mid int mid = ((l + r) >> 1)
#define InitO int &k, int l, int r
#define InitT int k, int l, int r
#define FR for (int i = head[u], v = e[i].to; i; i = e[i].next, v = e[i].to)
#define For(i, a, b) for (int i = a; i <= b; i++)
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0', ch = getchar();
    }
    return x * f;
}
void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

struct edge
{
    int next, to;
} e[_ << 1];
struct node
{
    int id, val;
    node() { id = val = 0; }
} tree[_ << 2];

int n, cnt, cot, top;
int head[_], dep[_], ls[_ << 2], rs[_ << 2], root[_], ans[_], stac[_ << 2];

int NewNode()
{
    if (top)
        return stac[top--];
    else
        return ++cot;
}
void add(int f, int t)
{
    e[++cnt] = edge{head[f], t};
    head[f] = cnt;
}

void dfs(int u, int f)
{
    dep[u] = dep[f] + 1;
    FR
    {
        if (v == f)
            continue;
        dfs(v, u);
    }
}
node pushup(node a, node b)
{
    if (!a.id)
        return b;
    if (!b.id)
        return a;
    if (a.val == b.val)
        return a.id < b.id ? a : b;
    else
        return a.val > b.val ? a : b;
}
void update(InitO, int x, int v)
{
    if (!k)
        k = NewNode();
    if (l == r)
        return (void)(tree[k].val += v, tree[k].id = x);
    Mid;
    if (x <= mid)
        update(lcon, x, v);
    else
        update(rcon, x, v);
    tree[k] = pushup(tree[lc], tree[rc]);
}
node query(InitT, int x, int y)
{
    if (!k)
        return node();
    if (x <= l && r <= y)
        return tree[k];
    Mid;
    node ans;
    if (x <= mid)
        ans = query(lcon, x, y);
    if (y > mid)
        ans = pushup(ans, query(rcon, x, y));
    return ans;
}
int merge(int a, int b, int l, int r)
{
    if (!a || !b)
        return a + b;
    if (l == r)
    {
        tree[a].val += tree[b].val;
        tree[b].id = tree[b].val = ls[b] = rs[b] = 0;
        stac[++top] = b;
        return a;
    }
    Mid;
    ls[a] = merge(ls[a], ls[b], l, mid);
    rs[a] = merge(rs[a], rs[b], mid + 1, r);
    tree[a] = pushup(tree[ls[a]], tree[rs[a]]);
    tree[b].id = tree[b].val = ls[b] = rs[b] = 0;
    stac[++top] = b;
    return a;
}

void dfs2(int u, int f)
{
    FR
    {
        if (v == f)
            continue;
        dfs2(v, u);
        root[u] = merge(root[u], root[v], 1, _);
    }
    update(root[u], 1, _, dep[u], 1);
    node c = query(root[u], 1, _, 1, _);
    ans[u] = c.id - dep[u];
}
int main()
{
    n = read();
    For(i, 1, n - 1)
    {
        int u, v;
        u = read();
        v = read();
        add(u, v);
        add(v, u);
    }
    dfs(1, 0);
    dfs2(1, 0);
    For(i, 1, n) write(ans[i]), puts("");
    return 0;
}

这份应该没判吧，我之前写的代码

by Biuld @ 2023-10-12 21:04:13

@Saka_Noa 感谢，对照了您的代码后，现在终于知道问题出在哪了

by Biuld @ 2023-10-12 21:06:26

在我线段树合并的 Dfs 中

inline void Dfs1(int now, int fath){
    dep[now] = dep[fath] + 1;
//  rt[now] = update(rt[now], 1, n, dep[now]);
    for(int i = head[now]; i; i = e[i].nxt){
        int v = e[i].to;

        if(v != fath){
            Dfs1(v, now);
            rt[now] = merge(rt[now], rt[v], 1, n);
        }
    }
    rt[now] = update(rt[now], 1, n, dep[now]);
    ans[now] = query(rt[now], 1, n) - dep[now];
}

update 本来是写在上面的，为先开新点再回收旧店，导致空间回收的效果微乎其微。
正确做法应是 update 新开点写在 merge 回收旧点后

by Cubic @ 2023-10-12 22:07:09

膜拜。