题解：P5773 [JSOI2016] 轻重路径

· · 题解

题目大意

有一棵 n 个点的以 1 为根的二叉树。有 q 次删点操作，每删掉一个叶子节点，需要动态的维护树的重链剖分。

在每次操作后输出所有重儿子的编号之和。

题解

这是一道 dfs 序+思维题。

显然地，删除一个叶子只可能影响到它的祖先中的重儿子。
直接 O(nd) 暴力可得 70 分，d 为树高。

考虑优化，可以用二分查找出从上一个点往下第一个会变为轻边的点（即这个点的子树大小小于等于上一个点的子树大小），不断查找直到找不到为止。

需要动态维护每个子树的大小，可用树状数组。

时间复杂度 O(n \log^3 n)。

Code

#include <bits/stdc++.h>

int n, q;

struct Tree{...}; //树状数组，支持单点修改，区间查询

Tree T;
int l[200010], r[200010], fa[200010][30], dep[200010];
int siz[200010], son[200010], dfn[200010], now = 0;

long long ans;
void dfs(int u)
{
    now++;
    dfn[u] = now;

    siz[u] = 1;

    if(l[u] != 0)
    {
        dep[l[u]] = dep[u] + 1;
        dfs(l[u]);
        siz[u] += siz[l[u]];
        fa[l[u]][0] = u;
    }
    if(r[u] != 0)
    {
        dep[r[u]] = dep[u] + 1;
        dfs(r[u]);
        siz[u] += siz[r[u]];
        fa[r[u]][0] = u;
    }

    if(siz[l[u]] > siz[son[u]])
    {
        son[u] = l[u];
    }
    if(siz[r[u]] > siz[son[u]])
    {
        son[u] = r[u];
    }

    ans += son[u];
}

int query(int u)
{
    return T.query(dfn[u], dfn[u] + siz[u] - 1);
}

int up(int u, int step){...} //倍增，从 u 点开始向上跳 step

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++)
    {
        scanf("%d %d", &l[i], &r[i]);
    }

    dfs(1);

    for(int j = 1; j <= 20; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            fa[i][j] = fa[fa[i][j-1]][j-1];
        }
    }

    scanf("%d", &q);

    for(int i = 1; i <= n; i++)
    {
        T.motify(dfn[i], 1);
    }

    printf("%lld\n", ans);

    for(int i = 1; i <= q; i++)
    {
        int u;
        scanf("%d", &u);

        T.motify(dfn[u], -1);

        int v = 1;
        while(1)
        {
            int L = 0, R = dep[u] - dep[v] - 1, len = -1;
            while(L <= R)
            {
                int mid = (L + R) / 2;
                if(query(up(u, mid)) <= query(v) / 2)
                {
                    len = mid;
                    L = mid + 1;
                }
                else
                {
                    R = mid - 1;
                }
            }

            if(len == -1)
            {
                break;
            }

            int pos1 = up(u, len);

            if(son[fa[pos1][0]] == pos1)
            {
                int pos2 = l[fa[pos1][0]] + r[fa[pos1][0]] - son[fa[pos1][0]];

                if(query(pos2) > query(pos1))
                {
                    ans -= pos1;
                    ans += pos2;
                    son[fa[pos1][0]] = pos2;
                }
                if(query(pos2) == 0 && query(pos1) == 0)
                {
                    ans -= pos1;
                    son[fa[pos1][0]] = 0;
                }
            }

            v = pos1;
        }

        printf("%lld\n", ans);

        if(l[fa[u][0]] == u)
        {
            l[fa[u][0]] = 0;
        }
        else
        {
            r[fa[u][0]] = 0;
        }
    }

    return 0;
}