1236 字

6 分钟

YZZX 集训笔记 Day3

2024-11-24

Notes

OI

树上问题#

树的直径#

树上两节点之间最长的简单路径是树的直径。

求法一：两次 DFS

从任意节点开始进行第一次 DFS，记录最远节点 $z$ ；再从节点 $z$ 开始进行第二次 DFS，记录最远节点 $z'$ 。 $z$ 和 $z'$ 的最短路径即为树的直径。

如果有负权则无法使用两次 DFS 求树的直径，而需要使用树形 DP。

Complete Code

求法二：树形 DP

对于树的直径，实际上是可以通过枚举从某个节点出发不同的两条路径相加的最大值求出。

Complete Code

树的中心#

树的重心#

树上算法#

最近公共祖先 LCA#

朴素算法#

每次找深度较大的那个点，使其向上跳。这样，两个点会交替上行，最终相遇，相遇位置即为 LCA。或者，先调整深度较大的那个点，将两个点深度统一之后一起向上跳，最终也会相遇。

倍增优化#

倍增算法可以用于改进朴素 LCA。

首先我们需要一个lowbit(n)函数。它是一个用于获取一个数的二进制表示中最低位的1及其后所有0构成的数值的函数。例如， $lowbit(20) = lowbit(10100)_2 = 100_2 = 4$ 。实现方法：

1
int lowbit(x){
2
    return x & -x;
3
}

建立fa[][]数组。fa[x][i]表示点 $x$ 的第 $2^i$ 个祖先。可以通过 DFS 预处理。

树上差分#

P3128 [USACO15DEC] Max Flow P

树上贪心#

[ABC333D] Erase Leaves Code

树形 DP#

P2014 [CTSC1997] 选课

P1122 最大子树和

P1352 没有上司的舞会

模板：

1
int dfs(int u){
2
    vis[u] = 1;
3
    //初始化
4
    for(int i = head[u]; i; i = e[i].nxt){
5
        int to = e[i].to;
6
        if(vis[to]) continue;
7
        dfs(to);
8
        //孩子->父亲，转移状态
9
    }
10
}

换根DP#

又叫二次扫描。

相比于一般的树形 DP：

以树上不同点为根，其解不同。
求解答案需要求解每个节点的信息。
无法通过一次搜索完成答案求解。
难度比一般树形 DP 要高。

P3478 [POI2008] STA-Station

给定一个 $n$ 个点的无根树，问以树上哪个节点为根时，其所有节点的深度之和最大？

如果以每个节点为根依次搜索一遍，时间复杂度为 $O(n^2)$ 。

考虑在第二次搜索时完成所有答案的统计。

第一次搜索，假设根节点为 $1$ 号节点，则此时只有 $1$ 号节点的答案已知。搜索过程中也需要统计出所有子树的大小。
第二次搜索，依然从 $1$ 号节点出发，如果 $1$ 号节点与 $x$ 节点相连，则考虑能否通过 $1$ 号节点的答案推出 $x$ 节点的答案。
假设此时根节点换为节点 $x$ ，此时子树由两部分构成，第一部分是原子树，第二部分是 $1$ 号节点的其它子树。
根节点从 $1$ 号节点变为节点 $x$ 的过程中，可以发现，第一部分深度降低了 $1$ ，第二部分深度增大了 $1$ 。
现在，可以通过第一次搜索得到的节点数量得出递推公式：

$ans[to] = ans[u] - siz[to] + (siz[1] - siz[to]), fa[to] = u$

1
void dfs(int u, int fa){
2
    dep[u] = dep[fa] + 1;
3
    dis[u]++;
4
    for(int i = head[u]; i; i = e[i].nxt){
5
        int to = e[i].to;
6
        if(to == fa) continue;
7
        dfs(to, u);
8
        dis[u] += dis[to];
9
    }
10
}
11
void dfs2(int u, int fa){
12
    for(int i = head[u]; i; i = e[i].nxt){
13
        int to = e[i].to;
14
        if(to == fa) continue;
15
        ans[to] = ans[u] - dis[to] + (dis[1] - dis[to]);
16
        dfs2(to, u);
17
    }
18
}

最长上升子序列 LIS#

P1020 [NOIP1999 提高组] 导弹拦截

模拟赛树专项#

[ABC165F] LIS on Tree #

树上LIS，用二分答案优化。

Complete Code

[ABC348E] Minimize Sum of Distances #

换根DP。

要求求最大直径最小，用二分答案求直径。

记录数组 $dp_u$ 表示在 $u$ 号点，其子树中所有点到达 $u$ 号点的最大链长。转移时，考虑其和子树之间的关系。

可以发现， $u$ 号点就类似于一个 LCA，两个最长的儿子拼起来的最长链就是这棵子树的最大直径。注意，这里的 $dp_v$ 中所存最长链均已保证子树内部合法。

接着考虑子树中直径超过二分的上限怎么办？贪心地想，我们肯定是要断掉最长的那条链，保留次长的。因为这样可以使得我们的总长度尽可能小，从而达到最优次数。最后，如果必须断边的次数大于上限 $s$ , 则不合格，应该调大区间，否则一定合格。想一想为什么。

1
void dfs(int u, int fa, int lim){
2
    int maxn = 0;
3
    for(int i = head[u]; i; i = e[i].nxt){
4
        int to = e[i].to;
5
        if(to == fa) continue;
6
        dfs(to, u, lim);
7
        if(dp[to] + maxn > lim){
8
            sum ++;
9
            maxn = min(maxn, dp[to]);
10
        } else maxn = max(maxn, dp[to]);
11
    }
12
    dp[u] = maxn + 1;
13
}