跳转至

长链剖分

对于一棵有根树，如果每个节点都向子树深度最大的儿子连一条重边，那么就会形成若干条长链，并且树上每个节点恰好被一条长链覆盖。这种剖分方式称为长链剖分。

长链剖分常用于优化深度相关的 dp，或者 \(O(1)\) 实现 \(k\) 级祖先查询（据说没有 \(O(\log\log n)\) 的倍增重链跑得快）。

优化 dp

长剖优化 dp 的核心做法是：将每条长链连续的存储在数组的一个区间上。一个节点的 dp 值直接继承其重儿子的 dp 值（同时进行偏移），然后再暴力合并所有轻儿子的长链。显然每条长链只在顶端节点的父亲处暴力处理一次，因此时间复杂度 \(O(n)\)。

CF1009F Dominant Indices

给定一棵 \(n\) 个节点的有根树。定义 \(f_{i,j}\) 表示 \(i\) 子树内距离 \(i\) 恰好 \(j\) 条边的节点数量。请你对每个 \(i\) 求出，\(f_{i,j}\) 取最大值时 \(j\) 的值。若有多个最大值，输出最小的 \(j\)。

\(n\le 10^6\)

考虑转移：

\[ f_{u,i}=\sum_{v\in to[u]}f_{v,i-1} \]

其中 \(f_{u,0}=1\)。由于第二维 \(i\) 始终不超过 \(u\) 子树的深度，因此考虑使用长链剖分。

我们在 dfs 中传递一个指针 f 表示要求儿子节点把 dp 数组放在 f 位置上。对于 \(u\) 的重儿子，我们传递 f' = f + 1。这样在重儿子递归结束后，其贡献就直接放进了 f 中。

然后枚举所有轻儿子，为它们分配空间并递归求解，然后暴力枚举轻儿子子树的深度（长链长度），将他们合并即可。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<iostream>
using namespace std;
const int N = 1e6 + 10;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n;
int dep[N], mxd[N], son[N];

void dfs1(int u, int fa) {
    mxd[u] = dep[u] = dep[fa] + 1;
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs1(v, u);
        mxd[u] = max(mxd[u], mxd[v]);
        if(mxd[v] > mxd[son[u]]) son[u] = v;
    }
}

int ff[N], ans[N];

void dfs2(int u, int fa, int *f) {
    f[0] = 1;
    int *cur = f;
    if(son[u]) {
        dfs2(son[u], u, cur + 1);
        cur += mxd[son[u]] - dep[u] + 1;
        ans[u] = ans[son[u]] + 1;
        if(f[0] >= f[ans[u]]) ans[u] = 0;
    } else {
        ans[u] = 0;
        return;
    }
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa || v == son[u]) continue;
        dfs2(v, u, cur);
        for(int i = 0; i < mxd[v] - dep[v] + 1; i++) {
            if(f[i + 1] + cur[i] > f[ans[u]]) ans[u] = i + 1;
            else if(f[i + 1] + cur[i] == f[ans[u]] && i + 1 < ans[u]) ans[u] = i + 1;
            f[i + 1] += cur[i];
        }
    }
}

int main() {

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs1(1, 0);
    dfs2(1, 0, ff);

    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';

    return 0;
}

P5904 [POI 2014] HOT-Hotels 加强版

给定一棵树，问有多少无序三元组 \((x,y,z)\) 满足 \(x,y,z\) 互不相同并且距离两两相等。

\(n\le 10^5\)

发现可以找到一个中心点满足三个点到该点距离相等。因此三个点形如两个点挂在中心点下面，另一个点挂在中心点上面；或者三个点都挂在中心点下面。后者可以归到前者处理。

考虑 dp，对于一个三元组 \((x,y,z)\)，我们在三个点的 \(\operatorname{lca}\) 处统计贡献（不是中心点）。因为长剖没法从父亲向儿子转移，因此没法处理上方节点的贡献。记 \(f_{i,j}\) 表示子树内到 \(i\) 距离为 \(j\) 的节点数量，\(g_{i,j}\) 表示 \(i\) 子树内已经选择了两个节点，要求剩下的一个节点到 \(i\) 距离为 \(j\)。容易转移：

\[ \begin{align*} f_{u,i}\times g_{v,i+1}+g_{u,i}+f_{v,i-1}&\to ans\\ f_{u,i}\times f_{v,i-1}&\to g'_{u,i}\\ f_{u,i}+f_{v,i-1}&\to f'_{u,i}\\ \end{align*} \]

\(f\) 直接用前一题的做法即可。对于 \(g\)，发现重儿子其实是向前偏移；而每个节点会占用从起始位置开始，长度等于子树深度的空间。因此一条重链占用的空间实际上等于重链长度的两倍。

我们可以用数组记录每个 \(g_u\) 的起始指针，节点的指针由其父亲决定。然后记录一个指针 ng 表示已经使用了多少空间。对于一条重链分配 \(2\times len\) 的空间，然后传入 g[v] = ng + len 将会落在空间的正中心。

代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#define int long long
using namespace std;
const int N = 1e5 + 10;

struct Edge {
    int v, next;
} pool[2 * N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, ans;
int dep[N], mxd[N], son[N];

void dfs1(int u, int fa) {
    dep[u] = dep[fa] + 1;
    mxd[u] = dep[u];
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa) continue;
        dfs1(v, u);
        mxd[u] = max(mxd[u], mxd[v]);
        if(mxd[v] > mxd[son[u]]) son[u] = v;
    }
}

int ff[N], gg[2 * N];
int *f[N], *g[N], *nf, *ng;

void dfs2(int u, int fa) {
    if(!son[u]) {
        f[u][0] = 1;
        g[u][0] = 0;
        return;
    }
    f[son[u]] = f[u] + 1;
    g[son[u]] = g[u] - 1;
    dfs2(son[u], u);
    f[u][0] = 1;
    ans += f[u][0] * g[u][0];
    for(int e = head[u]; e; e = pool[e].next) {
        int v = pool[e].v;
        if(v == fa || v == son[u]) continue;
        f[v] = nf;
        g[v] = ng += (mxd[v] - dep[v] + 1);
        nf += mxd[v] - dep[v] + 1;
        ng += mxd[v] - dep[v] + 1;
        dfs2(v, u);
        for(int j = 0; j < mxd[v] - dep[v] + 1; j++) {
            ans += g[u][j + 1] * f[v][j];
            if(j) ans += f[u][j - 1] * g[v][j];
        }
        for(int j = 0; j < mxd[v] - dep[v] + 1; j++) {
            g[u][j + 1] += f[u][j + 1] * f[v][j];
            if(j) g[u][j - 1] += g[v][j];
            f[u][j + 1] += f[v][j];
        }
    }
}

signed main() {

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    dfs1(1, 0);

    nf = ff;
    ng = gg;

    f[1] = nf;
    g[1] = ng += (mxd[1] - dep[1] + 1);
    nf += mxd[1] - dep[1] + 1;
    ng += mxd[1] - dep[1] + 1;

    dfs2(1, 0);

    cout << ans << '\n';

    return 0;
}