图论基础1

ql12345 · 2024-02-01 16:03:11 · 个人记录

图论基础预备知识

概念：图（边的有向/无向、边权）、连通分量、连通图、环、环的性质

邻接矩阵建图（一般不用）、邻接表建图（vector实现）、链式前向星建图（数组/struct实现）、基础dfs

三种建图方式的代码实现：

邻接矩阵

int dis[N][N];

for (int i = 1; i <= m; i ++) {
    cin >> a >> b >> c;
    dis[a][b] = c; // 如果a,b之间有不止一条边，则dis[a][b]的值要具体问题具体讨论
}

邻接表

vector<pair<int, int> > edges[N];

for (int i = 1; i <= m; i ++) { // 建图
    cin >> a >> b >> c;
    edges[a].push_back(make_pair(b, c));
}

for (int i = 1; i <= n; i ++) // 查询
    for (int j = 0; j < edges[i].size(); j ++) {
        to = edges[i][j].first;
        w = edges[i][j].second;
    }

链式前向星

int head[N], cnt;
struct Edges{
    int to, w, nxt;
} edges[M << 1];

void add_edge(int from, int to, int w) { // 建图
    edges[++ cnt].to = (Edges){to, w, head[from]};
    head[from] = cnt;
}
for (int i = 1; i <= m; i ++) {
    cin >> a >> b >> c;
    add_edge(a, b, c);
}

for (int i = 1; i <= n; i ++) // 查询
    for (int j = head[i]; j; j = edges[j].nxt) {
        to = edges[j].to;
        w = edges[j].w;
    }

树的概念与性质

以下所考虑的所有图都默认没有重边和自环、只有无向边，即简单无向图。

树的等价描述

命题1：有n个节点的连通图至少有n-1条边。

证明：每条边最多将两个不连通的部分变成连通的，所以最多减少一个连通块。n个孤立的节点为n个连通块，将其变成一个连通块至少需要n-1条边。

定义1：对于一个有n个节点n-1条边的连通图，定义其为树。

命题2：树\Longleftrightarrow给定节点构成的所有连通图中边数最少的一类情况。（由命题1和定义1易得）

命题3：对于一个连通图，树\Longleftrightarrow无环。

证明：\Longrightarrow：假设有环，则断掉环上任意一条边，由环的性质知这条边的两个端点之间仍有至少一条简单路径，即仍属于同一个连通块。故所有点仍然连通，这是仍然是一个连通图，与命题2矛盾，故假设不成立。\Longleftarrow：假设无环且不是一颗树，那么有至少n条边，从而至少有一条边的加上并没有减少连通块。这条边连接了同一个连通块中的两个点，这两个点之间存在两条不相交的简单路径，从而存在一个环，矛盾，故假设不成立。

命题4：树\Longleftrightarrow任意两个节点之间有且仅有一条简单路径。

证明：\Longrightarrow：由连通知存在，只需证唯一。若存在两个节点之间简单路径不唯一，则任取两条不同的简单路径，不妨设这两条简单路径只在这两个节点相交（否则取两条简单路径的两个相邻交点）。这两条简单路径构成一个环，与命题3矛盾，故假设不成立。\Longleftarrow：由存在知连通，若不是树，则由命题3知存在至少一个环，任取一个环，环上任意两点之间具有不止一条简单路径，与条件矛盾，故假设不成立。

树与图

首先先明确：树是一种特殊的图，进一步地，树是一种特殊的无向连通图。

命题5：任意一个不是树的连通图一定存在一条边，去掉它之后仍然是连通图。

证明：由命题3知该连通图中存在至少一个环，去掉该环上的任意一条边即可。

定义2：一个连通图如果能去掉几条边（可以为0条）变成一棵树，则这颗树称为该连通图的生成树。（显然一个连通图的生成树不一定唯一）

命题6：任意一个连通图都存在生成树。（由命题2和命题5易得）

有根树与无根树

作为一个图而言，树的任何一个点都可以是根，确定根以后就可以确定节点的父子关系。确定了根节点的树称为有根树，否则称为无根树。显然，一个节点有编号的（无根）树有n种合法的父子关系（分别对应n个节点为根的情况）。

树的遍历与dfs序

现在考虑一个已经确定了根的树，从根开始沿着已有的边做dfs。在图论中的dfs需要我们确定下一个访问的点没有被访问到过，由于树中不存在环，所以我们不需要像一般图那样记一个visit数组，只需要判断一下下一个访问的点不是父节点就行了。

通过dfs，我们可以初步获得如下信息：每一个节点的子节点集合、父节点（祖先集合）、深度、度、子树大小、dfs序编号、子树深度等。根据题目的具体需求，我们甚至还可以获得子树中最长链长度、次长链长度等更加复杂信息，树形dp就是在树上dfs的一种推广。

需要考虑的一个问题是，实际问题中我们往往遇到的是无根树，那随意确定一个根开始的dfs所得到的信息是否在无根树的意义下同样有意义呢？答案是肯定的，比如子树大小实际上就是该节点切段其到父节点那一条边之后所能到的点的数量。dfs究竟能求出那些信息和这些信息如何加以利用需要具体问题具体考虑。

树上dfs的代码实现：

int dep[N], siz[N], dfn[N], fa[N], num, maxsiz[N];
 // 以维护深度、子树大小、dfs序、父节点、最大的儿子子树的大小为例

void dfs(int now, int father) {
    dep[now] = dep[father] + 1;
    siz[now] = 1;
    dfn[now] = ++ num;
    fa[now] = father;
    for (int i = head[now]; i; i = edges[i].nxt)
        if (edges[i].to != father) {
            dfs(edges[i].to, now);
            siz[now] += siz[edges[i].to];
            maxsiz[now] = max(maxsiz[now], siz[edges[i].to]);
        }
    return;
}
dfs(1, 0); // 以1为根开始dfs

关于dfs序的一个结论：一个子树的dfs序是连续的一段。如果是前序遍历，那dfs序中的第一个数是子树的根，如果是后序遍历则最后一个数是子树的根。

有一些题可以利用这个性质将树上的问题转化为序列上的问题来解决。

例题

P5908 猫猫和企鹅：树的遍历求节点深度

P2420 让我们异或吧：树的遍历求异或前缀和

P1351 [NOIP2014 提高组] 联合权值：dfs维护每个节点所连节点中最大的两个权值和所连节点权值和

最近公共祖先 LCA

现在考虑一棵有根树，树上任意两个点之间的简单路径怎么找呢？如果这两个点中的一个是另一个点祖先，则从那个后代一路向上就可以到达这个点。如果两个点都不是对方的祖先呢，沿用刚才的想法，可以从一个点到达公共的祖先，再从这个公共祖先到达另一个点。由于有简单路径的要求，所以我们要找到距离两个点最近的公共祖先，也就是深度最小的公共祖先，最近公共祖先简称 LCA（Lowest Common Ancestor）。完全一样地，我们也可以定义一个点集的最近公共祖先。

LCA有以下几条性质：

命题1：LCA(\{u\})=u。

命题2：LCA(u,v)=u\Leftrightarrow u是v的祖先。

命题3：两点集并的LCA为两点集分别的LCA的LCA。

命题4：两点的LCA在两点之间的最短路（唯一）上。

命题5：dis(u,v)=dep(u)+dep(v)-2\times dep(LCA(u,v))。

倍增求LCA

求LCA的方法主要有倍增和树剖。倍增的时间复杂度是O(n\mathrm{log}n)的预处理+O(\mathrm{log}n)的单次查询，树剖的时间复杂度是O(n)的预处理+O(\mathrm{log}n)的单次查询，且树剖的常数较小。倍增的空间复杂度是O(n\mathrm{log}n)，树剖的空间复杂度是O(n)。但是树剖较难，我们这次只讲倍增方法。

先考虑朴素的求LCA(a,b)的方法：

如果a和b的深度不同，就让深度大的那一个（假设为a）不断做a=fa[a]直到深度相同
如果此时a==b就说明b是原本的a的祖先，b即是LCA
如果此时a!=b就不断做a=fa[a],b=fa[b]直到a==b，此时即是LCA

这样做单次查询的复杂度是O(n)的。考虑这个方法里有两次向上跳的过程，而且每次向上跳的终点都是固定的，所以可以使用倍增一次跳很多步来优化掉一步一步跳。

倍增的思想你们都学过了，比如凑出19（二进制为10011）的重量，只需要重量为16、2和1三个砝码就够了，而只需要重量为1,2,\cdots,2^k的k个砝码就能够凑出0\sim 2^{k+1}-1的2^{k+1}个重量了。具体的做法是用从大到小的砝码去试（二进制表示下从高位到低位查找1），如果小于该数（即该数的二进制表示下该位为1）就用该数减去这个砝码，直到该数变为0（二进制表示下的每一个1都被减去了）。显然，这样做不会漏掉任何二进制表示下的任何一位数，所以一定能够准确地凑出该数。

而用倍增的思想优化朴素方法中的一步一步跳就是用若干个一次跳2^k步来减少跳的次数。这需要我们预处理出来从每个点开始往上跳2^k步的终点（数组的名字仍记作fa）。

预处理可以采用递推的方法，一方面按dfs的顺序从根节点往下递推、一方面k从小往大递推。根节点往上跳任意步都是0，每个节点往上跳1步是fa[a][0]即自己的父节点，往上跳2^k步的终点为往上跳2^{k-1}步的终点往上跳2^{k-1}步的终点，而该点往上跳2^{k-1}步的终点和该终点处的fa数组都已经预处理好了，所以可以直接使用。

代码实现：

预处理

int n, rt, dep[N], fa[N][30]; // rt：根节点
vector<int> edges[N];

void dfs(int x) {
  for (int i = 0; i < edges[x].size(); i ++) {
    int y = edges[x][i];
    if (dep[y]) continue;

    dep[y] = dep[x] + 1, fa[y][0] = x;
    for (int k = 1; (1 << k) <= n; k ++) // 按k从小到大递推
      fa[y][k] = fa[fa[y][k - 1]][k - 1]; // 利用递推关系直接得到
    dfs(y); // 按dfs顺序递推，处理完y再处理y的后代
  }
}
void get_fa_dfs() {
  dep[rt] = 1;
  dfs(rt);
}

查询

int Lca(int a, int b) {
  if (dep[a] < dep[b]) swap(a, b); // 让a是深度大的那一个，让a往上跳
  for (int k = 25; k >= 0; k --)
    if (dep[fa[a][k]] >= dep[b]) a = fa[a][k]; // a跳到和b同一个高度
  if (a == b) return b; // 如果a==b就说明b是原来的a的祖先，返回b即可
   // 如果a!=b就让a和b同时往上跳，直到跳到一块
  for (int k = 25; k >= 0; k --)
    if (fa[a][k] != fa[b][k]) a = fa[a][k], b = fa[b][k];
     // fa[a][k]==fa[b][k]相当于需要凑的步数的二进制表示下第k位为0，不跳，不等于的时候才跳
     // 这样处理会使得我们永远也跳不到LCA，因为只凭fa是否相等无法判断跳到的那个点是LCA还是LCA的祖先，所以我们跳的终点实际上是LCA的下面一个点
  return fa[a][0]; // 输出的时候也要输出跳的终点的上面一个点
}

例题

树上问题大都离不来LCA，只要提到树上两点之间的路径就需要LCA，而考虑树上一段路径上的问题的题很常见（处理这类题还有一个很常用的以后会学的方法是树链剖分）。树上差分本质上也是利用了树上两点之间的路径，所以也需要用到LCA。

另外，很多题目就算没有明着提到树上两点之间的路径，但是会涉及到树上的距离，从而就也需要考虑LCA。

P3379 【模板】最近公共祖先（LCA）：板子

P5836 [USACO19DEC] Milk Visits S：倍增求LCA的时候同倍增数组一样地多维护一个“该跳跃区间是否存在某奶牛的数组”

P4281 [AHOI2008] 紧急集合 / 聚会：求出三个点两两LCA中只出现一次的那个LCA即是集合点，利用命题5计算距离即可（考虑证明）

树的直径

定义1：树上的最长链为树的直径。

有时也简称树的直径的长度为树的直径，显然，树的直径不一定唯一，但树的直径的长度一定唯一。

树的直径的题目中多是需要想出结论才能做的（就连两遍dfs求树的直径的方法都需要证明中间结论），所以猜结论和证明结论很重要。证明和树的直径有关的结论的常用思路是反证法，假设结论不成立，在所有不满足结论的情形下分别构造出一条比直径更长的链，从而证得结论成立。

树的直径有以下几条性质：

命题1：树的直径的端点一定是叶节点（度数为1）。

命题2：对于边权为1的树，如果树的直径不止一条，则直径的长度一定为偶数，且所有直径的中点重合。（考虑反证）

命题3：边权为正的树，如果树的直径不止一条，则所有直径的中点重合，并且中点延伸出的任意直径的一半长度均相等。

命题4：以任意一点为根开始dfs，深度最大的点一定是一个树的直径的端点。（考虑反证）

两遍dfs求树的直径

先以任意点为根先dfs一遍找出深度最大的点，由命题3，这是树的直径的端点，所以从这个点开始再dfs一遍找到深度最大的点，就是这条直径的另一端。

代码实现：

int n, dep[N], s, maxdep;
vector<int> edges[N];

void dfs(int now, int fa) {
    for (int i = 0; i < edges[now].size(); i ++) {
        int y = edges[now][i];
        if (y == fa) continue;
        dep[y] = dep[now] + 1;
        maxdep = max(maxdep, dep[y]); // maxdep是dfs找到的最大深度
        dfs(y, now);
    }
}

dfs(1, 0);
for (int i = 1; i <= n; i ++)
    if (dep[i] == maxdep) s = i; // s是第一遍dfs找到的最远点
dep[s] = 0; // 根节点的深度为0，从而深度就是到根节点的距离
dfs(s, 0);
printf("%d", maxdep);

树形dp求树的直径

用树形dp可以通过一遍dfs维护出来（任意确定了一个根之后）每个节点向下距离最远和第二远的距离（这两个距离不能是同一个子节点贡献的），每个点的这两个距离相加的最大值就是答案（该点是一个树的直径两端点的LCA）。

代码实现：

int n, dep1[N], dep2[N], maxdep;
vector<int> edges[N];

void dfs(int now, int fa) {
    for (int i = 0; i < edges[now].size(); i ++) {
        int y = edges[now][i];
        if (y == fa) continue;
        dfs(y, now);
        if (dep1[y] + 1 > dep1[now]) {
         // y的子树内只能贡献now的至多一条长链，所以要用dep1[y]，先和dep1比较，再和dep2比较
            dep2[now] = dep1[now];
            dep1[now] = dep1[y] + 1;
        }
        else if (dep1[y] + 1 > dep2[now])
            dep2[now] = dep1[y] + 1;
    }
}

dfs(1, 0);
for (int i = 1; i <= n; i ++)
    maxdep = max(maxdep, dep1[i] + dep2[i]);
printf("%d", maxdep);

两种方法比较

两遍dfs的方法的好处在于能够记录直径上的路径，但不能处理边权为负的情况，而且只能求出一条树的直径；

树形dp的方法的好处在于能够处理边权为负的情况，而且可以求出全部树的直径，但不能记录具体的路径。

实际做题中需要根据题目选择使用哪个方法。

例题

PT07Z - Longest path in a tree：板子

P2195 HXY造公园：树的直径的定义，求出初始树的直径初始化并查集，然后做并查集合并、查询操作即可

P5536 【XR-3】核心城市：树的直径的性质+树上dfs，先找到树的直径的中心然后dfs找子树深度最大的依次贪心即可（贪心策略考虑证明）

P1099 [NOIP2007 提高组] 树网的核：贪心求直径上距两端距离最大值最小的一段即可（考虑证明）

P4408 [NOI2003] 逃学的小孩：贪心，AB为直径两端，C遍历着找即可（考虑证明贪心结论）

P3629 [APIO2010] 巡逻：第一条路建直径两端，第二条路将第一条路上权改为-1后树形dp找出直径（分别考虑证明第一条路和第二条路正确性）

树的重心

对于一个无根树，子树的含义为去掉该点后分成的若干个连通块（均是树）。

定义1:无根树上最大子树最小的点是树的重心。

显然，树的重心一定存在但不一定唯一，重心的最大子树的大小唯一。（例：两个点的树）

树的重心的题目和树的直径的题目一样，需要使用结论，下面列出几条常用的性质。在证明有关树的重心的结论的时候，也是采用反证法，构造出更优的“重心”或者说明不存在更优的“重心”。

命题1：树的重心\Longleftrightarrow所有子树大小均不超过整颗树大小的一半。

证明：\Longrightarrow：若u是一个树的重心且以它为根有子节点v的子树超过整颗树大小的一半，那么以v为根，u的子树大小一定不超过整颗树大小的一半，且v的其他子节点的子树大小显然都小于原本v的子树大小。即v的最大子树比u的最大子树严格小，与u是重心矛盾。\Longleftarrow：若u的所有子树大小都不超过整颗树大小的一半，以u为根，其他任意点的子树中包含u的子树一定也包含除该点所在的u的子树以外的所有子树，从而该包含u的子树的大小不小于整颗树大小的一半，故不会比u更优，故u是树的重心。

命题2：如果树的重心不唯一，则只有以下一种情形：，即有且仅有相邻的1,2两个点是树的重心，断掉两点之间的边之后为两个相同大小的树。

证明：以一个重心u为根，如果存在另一个重心v，则找能使得v的包含u的子树大小不超过整颗树的一半（等于整颗树的一半）的情形即可。

命题3：用一条边将两棵树连接起来，新的重心在原来分别的重心的连线上。

证明：只证明两棵树重心都唯一的情形，其他情形由该情形下的证明易证得。对于分别的重心连线以外的点（不妨设该点属于树1），以该点为根则树1的重心和树2全部在同一棵子树内，而其他子树大小总和都小于树1大小的一半，从而包含树1重心的那棵子树的大小大于树1加树2大小总和的一半。

命题4：如果一个树增添或删去一个叶子，则树的同一个重心最多移动一个节点。（证明不难，留作思考）

命题5：树中所有点到某个点的距离和中，到重心的距离和是最小的。

证明：调整法，以树的重心u为根，对于它的任意一个子节点v比较所有点到该点的距离和。设v的子树内所有点到v的距离和为d_1，除了v的子树以外的所有点到u的距离和为d_2，所有点到v的距离和为d_1+d_2+n-size_v，所有点到u的距离和为d_1+d_2+size_v，由size_v和n-size_v的大小关系知所有点到u的距离和更小。对于其他任意点，可以通过不断和父节点比较得到以下结论：“以u为根每一点的距离和严格小于父节点（除了该点也是树的重心的情况）”。

注：以上的定义和命题均是对点权为1、边权为1的树讨论的，对于点权和边权为任意正数的树，定义和命题1、2、3、5都可完全一致地得到（同样的证明）（此时的子树大小size不再是点数，而是点权和，距离则是点权乘以边权）。

求树的重心

由命题1，要求树的重心只需要从任意点开始dfs一遍记录一下每个点的子树大小和子树最大的子节点的子树大小，然后判断该点最大子树大小（子树最大的子节点的子树大小和整颗树大小减去自身子树大小的最大值）是否超过整颗树大小的一半即可。

代码实现：

int n, siz[N], maxsiz[N], ans;
vector<int> edges[N];

void dfs(int now, int fa) {
    siz[now] = 1;
    for (int i = 0; i < edges[now].size(); i ++) {
        int y = edges[now][i];
        if (y == fa) continue;
        dfs(y, now);
        maxsiz[now] = max(maxsiz[now], siz[y]);
        siz[now] += siz[y];
    }

    if (max(maxsiz[i], n - siz[i]) * 2 <= n) // 判断是不是重心
        printf("%d ", i);
}

例题

P1395 会议：板子

P1364 医院设置：带点权的树的重心，确定重心之后dfs一遍求最小距离即可

Kay and Snowflake：第二次dfs求树的重心的时候求出每个节点子树的重心，由树的重心的性质，只需从子节点子树重心位置往上枚举即可（考虑利用树的重心的性质证明）

Link Cut Centroids：若重心不唯一，删一个叶节点加到另一个重心上即可（考虑重心不唯一的树的结构、考虑证明这样做的正确性）

树上差分和前缀和

在让我们异或吧这道题中我们已经使用过树上前缀和的思想了，类比序列差分和前缀和，树上差分和树上前缀和解决的问题是对于树上的一段路径（对应序列里的区间）的修改和查询。

树上差分：路径加上同一个数：O(\mathrm{log}n)，查询单点/边的值：O(n)，适合修改多查询少的问题。

树上前缀和：路径加上同一个数：O(n)，查询单点/边的值：O(\mathrm{log}n)，适合修改少查询多的问题。

树上前缀和

考虑维护树上的点权，每一个点i处记录w_i=从根节点到该点的路径上所有点权之和。

初始化：dfs

查询$a$到$b$的路径上所有点的点权和：$sum=w_a+w_b-w_{LCA(a,b)}-w_{fa[LCA(a,b)]}

如果维护的是树上的边权，用边的深度较大的那个节点的点权来记录边权即可。注意此时查询a到b的路径上所有边的边权和：sum=w_a+w_b-2w_{LCA(a,b)}。

树上差分

考虑维护树上的点权，每一个点i处记录w_i=该点点权-除该点外子树内所有点点权和。

初始化：dfs

a$到$b$的路径上所有点加上$x$：$w_a+=x,w_b+=x,w_{LCA(a,b)}-=x,w_{fa[LCA(a,b)]}-=x

查询任意点的点权：dfs一遍求出每个点子树的w_i之和即可

如果维护的是树上的边权，用边的深度较大的那个节点的点权来记录边权即可。注意此时a到b的路径上所有点加上x：w_a+=x,w_b+=x,w_{LCA(a,b)}-=2x。

代码实现：（点差分板子Max Flow P）

void get_sum_dfs(int x, int F) {
    for (int i = 0; i < G[x].size(); ++i) {
        int y = G[x][i];
        if (y == F) continue;
        get_sum_dfs(y, x);
        point[x] += point[y];
    }
    ans = max(ans, point[x]);
}

for (int i = 1, x, y; i <= m; ++i) {
        x = read(), y = read();
        int t = lca(x, y);
        ++ point[x], ++ point[y];
        -- point[t], -- point[fa[t][0]];
    }

例题

P3128 [USACO15DEC] Max Flow P：点差分板子

P3258 [JLOI2014] 松鼠的新家：点差分板子，第一条路径首尾都加1，最后一条路径首尾都不加，其他路径尾加首不加

P6869 [COCI2019-2020#5] Putovanje：边差分板子，每条路径上的边加1，dfs一遍算出每条边的费用（单程票or多程票）求和即可

P8805 [蓝桥杯 2022 国 B] 机房：树上前缀和板子

模拟赛

P2052 [NOI2011] 道路修建：黄，树的遍历

P4427 [BJOI2018] 求和：绿（实际难度黄到绿），树上前缀和。k从1到50维护每个节点深度k次方前缀和

P6374 「StOI-1」树上询问：蓝（实际难度为绿），LCA

P2491 [SDOI2011] 消防：紫（但是是讲过的原题），树的直径。题解参考树网的核