线段树合并解法6分可能原因

可能是在dfs的时候先合并后insert当前节点

会修改不应该修改的节点

新增节点式的合并也会宝玲.

举个例子

宝玲:

void dfs(int x, int fa, int dep)
{
    siz[x] = 1;
    deep[x] = dep;
    for (int i = head[x]; i; i = nex[i])
    {
        int y = ver[i];
        if (y == fa) continue;
        dfs(y, x, dep + 1);
        siz[x] += siz[y];
        rt[x] = merge(rt[x], rt[y]);
    }
    insert(rt[x], 1, n, dep, siz[x] - 1);
}

AC:

void dfs(int x, int fa)
{
    siz[x] = 1;
    for (int i = head[x]; i; i = nex[i])
    {
        int y = ver[i];
        if (y == fa) continue;
        dfs(y, x);
        siz[x] += siz[y];
    }
}

void dfs2(int x, int fa, int dep)
{
    insert(rt[x], 1, n, dep, siz[x] - 1);
    deep[x] = dep;
    for (int i = head[x]; i; i = nex[i])
    {
        int y = ver[i];
        if (y == fa) continue;
        dfs2(y, x, dep + 1);
        rt[x] = merge(rt[x], rt[y]);
    }
}