题解【洛谷P3884】[JLOI2009]二叉树问题

题面

题解

这道题目可以用很多方法解决，这里我使用的是树链剖分。

关于树链剖分，可以看一下我的树链剖分学习笔记。
大致思路是这样的：

1. 第\(1\)次\(dfs\)记录出每个点的父亲、重儿子、深度、子树大小；
2. 第\(2\)次\(dfs\)优先遍历重儿子，记录出点所在链的链顶和重新遍历后的\(dfs\)序；
3. 计算出最大的深度及宽度；
4. 树链剖分求\(\texttt{LCA}\)并计算点对之间的距离。

具体实现还要注意细节。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#define itn int
#define gI gi

using namespace std;

inline int gi()//快速读入
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar();}
    return f * x;
}

int n, m, tot, head[103], nxt[2003], ver[2003];
int dep[103], sz[103], fa[103], son[103], dfn[103], top[103], pre[103], p[103];
int max_dep, max_h;

inline void add(int u, int v)
{
    ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;//邻接表存图
}

void dfs1(int u, int f)
{
    fa[u] = f/*记录父亲*/, dep[u] = dep[f] + 1/*计算深度*/, sz[u] = 1/*子树大小*/;
    int maxsize = -1;
    for (itn i = head[u]; i; i = nxt[i])
    {
        int v = ver[i];
        if (v == f) continue;
        dfs1(v, u);//遍历
        sz[u] = sz[u] + sz[v];//子树大小计算
        if (sz[v] > maxsize) maxsize = sz[v], son[u] = v;//记录重儿子
    }
}

int tim;

void dfs2(int u/*当前节点*/, int f/*当前节点所在链的链顶*/)
{
    top[u] = f/*记录链顶*/, dfn[u] = ++tim/*重新遍历后的dfs序*/;
    if (!son[u]) return;//没有重儿子说明是叶子结点,直接返回
    dfs2(son[u], f);//优先遍历重儿子
    for (itn i = head[u]; i; i = nxt[i])
    {
        int v = ver[i];
        if (v == fa[u] || v == son[u]) continue;//已经处理过了就直接返回
        dfs2(v, v);//继续剖分链
    }
}

int main()
{
    n = gi();
    for (int i = 1; i < n; i+=1)
    {
        int u = gi(), v = gi();
        add(u, v), add(v, u);//存图,注意是双向边
    }
    dfs1(1, 0);//树链剖分第1次dfs
    dfs2(1, 1);//第2次dfs
    for (itn i = 1; i <= n; i+=1)
    {
        max_dep = max(max_dep, dep[i]);//计算最大深度
        ++p[dep[i]];//开一个桶记录当前深度的点数
    }
    for (int i = 1; i <= max_dep; i+=1)
    {
        max_h = max(max_h, p[i]);//计算最大宽度
    }
    printf("%lld\n%lld\n", max_dep, max_h);//输出
    int U, u = gi(), V, v = gi(), lca = 0;//输入
    U = u, V = v;
    while (top[u] != top[v]) 
    {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    if (dep[u] < dep[v]) lca = u; else lca = v;//树链剖分计算LCA
    printf("%lld\n", 2 * (dep[U] - dep[lca]) + dep[V] - dep[lca]);//输出点对距离,注意要*2
    return 0;//结束
}

题解【洛谷P3884】[JLOI2009]二叉树问题

原文：https://www.cnblogs.com/xsl19/p/11389070.html