前置知识

树基础

存图方式

$\texttt{vector}$ 存图

1
2
3
4
// 增加单向边 (x,y)
vector<int> g[N];
cin>>x>>y;
g[x].push_back(y);

$\texttt{vector}$ 遍历

1
2
3
4
5
6
// 遍历与 x 相邻的点
for(int i=0;i<g[x];++i)
{
    int y=g[x][i];// 下一个遍历的点
    // ...
}

链式前向星 存图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 增加单向边 (x,y)，边值为 w
struct arr
{
    int to,w,next;
}edge[N];
int head[N];
void add(int x,int y,int w)
{
    cnt++;
    edge[cnt].next=head[x];
    head[x]=cnt;
    edge[cnt].to=y;
    edge[cnt].w=w;// 存边值
}
int main()
{
    cin>>x>>y;
    add(x,y);
}

链式前向星 遍历

1
2
3
4
5
6
// 遍历与 x 相邻的点
for(int i=head[x];i;i=edge[i].next)
{
    int y=edge[i].to;// 下一个遍历的点
    // ...
}

注：画图工具 CS Academy

树的直径

定义

树上任意两节点之间最长的简单路径即为树的直径。

如何求

一个做法是两遍 $\texttt{DFS}$，还有一个做法是树形 $\texttt{DP}$。

两遍 $\texttt{DFS}$

首先从任意节点 $x$ 开始 $\texttt{DFS}$，到达距离其最远的节点，记为 $y$。

再从 $y$ 开始 $\texttt{DFS}$，到达距离其最远的节点，记为 $z$。

可以知道 $y,z$，即为直径的两端点。

证明与树形 $\texttt{DP}$ 方法见 OI Wiki。

两遍 $\texttt{DFS}$ 不能处理负权图。 

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
void dfs1(int k,int fa)
{
    if(d[k]>ma)
    {
        ma=d[k];
        am=k;
    }
    for(int i=0;i<g[k].size();++i)
    {
        if(g[k][i]==fa) continue;
        d[g[k][i]]=d[k]+1;
        dfs1(g[k][i],k);
    }
}
void dfs2(int k,int fa)
{
    if(d[k]>ma)
    {
        ma=d[k];
        am=k;
    }
    for(int i=0;i<g[k].size();++i)
    {
        if(g[k][i]==fa) continue;
        d[g[k][i]]=d[k]+1;
        f[g[k][i]]=k;
        dfs2(g[k][i],k);
    }
}
int main()
{
    dfs1(1,0);// 从节点 1 开始 DFS
    dfs2(am,0);// 从搜到的节点开始 DFS
    // am 就是直径的一个端点
}

最近公共祖先

定义

最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
为了方便，我们记某点集 $S=\{v_1,v_2,\ldots,v_n\}$ 的最近公共祖先为 $\text{LCA}(v_1,v_2,\ldots,v_n)$ 或 $\text{LCA}(S)$。

性质

  1. $\text{LCA}(\{u\})=u$；
  2. $u$ 是 $v$ 的祖先，当且仅当 $\text{LCA}(u,v)=u$；
  3. 如果 $u$ 不为 $v$ 的祖先并且 $v$ 不为 $u$ 的祖先，那么 $u,v$ 分别处于 $\text{LCA}(u,v)$ 的两棵不同子树中；
  4. 前序遍历中，$\text{LCA}(S)$ 出现在所有 $S$ 中元素之前，后序遍历中 $\text{LCA}(S)$ 则出现在所有 $S$ 中元素之后；
  5. 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 $\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))$；
  6. 两点的最近公共祖先必定处在树上两点间的最短路上；
  7. $d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))$，其中 $d$ 是树上两点间的距离，$h$ 代表某点到树根的距离。

求法

首先可以想到让深度大的那个点先往上跳，直到两点深度相同，再同时往上跳，显然在一颗树上，两点必定相遇。

复杂度为 $O(n)$。

但这样复杂度显然不优，考虑优化。

可以考虑倍增，预处理 $\text{fa}_{x,i}$ 数组，表示点 $x$ 的第 $2^{i}$ 个祖先。

可以通过 $\texttt{DFS}$ 预处理。

在向上跳的过程中，因为要先将 $u,v$ 两点跳到深度相同的位置，可以先计算出 $u,v$ 两点的深度差，深度在 $\texttt{DFS}$ 的过程中也能预处理出来。设深度差为 $y$，通过将 $y$ 进行二进制拆分，我们将跳的次数转换为 「$y$ 的二进制表示所含 1 的个数」。

同时往上跳的过程中，我们从最大的 $i$ 开始循环尝试，一直尝试到 $0$（包括 $0$），如果 $\text{fa}_{u,i}\not=\text{fa}_{v,i}$，则 $u\gets\text{fa}_{u,i},v\gets\text{fa}_{v,i}$，那么最后的 LCA 为 $\text{fa}_{u,0}$。

倍增算法的预处理时间复杂度为 $O(n \log n)$，单次查询时间复杂度为 $O(\log n)$。

例题

【模板】最近公共祖先

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
#include<bits/stdc++.h>
using namespace std;
vector<int> g[500002];
int n,m,s;
int x,y;
int f[500002][22];
int d[500002];
int lg[500002];
void dfs(int k,int fa)
{
    f[k][0]=fa;
    d[k]=d[fa]+1;
    for(int i=1;i<=lg[d[k]];++i) f[k][i]=f[f[k][i-1]][i-1];
    for(int i=0;i<g[k].size();++i)
    {
        if(g[k][i]==fa) continue;
        dfs(g[k][i],k);
    }
}
int LCA(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    while(d[x]>d[y]) x=f[x][lg[d[x]-d[y]]-1];
    if(x==y) return x;
    for(int i=lg[d[x]]-1;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<n;++i)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    dfs(s,0);
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        cout<<LCA(x,y)<<"\n";
    }
    return 0;
}

Max Flow P

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
// 考虑差分
// 树上区间 [x,y] 都加 1
// 相当于 sum[x]+1,sum[y]+1,sum[lca(x,y)]-2
// 但 lca(x,y) 上 +2 又 -2 相当于没变，考虑将 sum[fa[lca(x,y)]]-1
// fa[x] 表示 x 的父节点
// 于是变成了 sum[x]+1,sum[y]+1,sum[lca(x,y)]-1,sum[fa[lca(x,y)]]-1
// 用倍增求 LCA
// 遍历整棵树统计和即可
#include<bits/stdc++.h>
using namespace std;
vector<int> g[50002];
int n,m;
int x,y;
int ans;
int sum[50002];
int lg[50002],f[50002][32];
int d[50002];
void dfs(int k,int fa)
{
    f[k][0]=fa;
    d[k]=d[fa]+1;
    for(int i=1;i<=lg[d[k]];++i) f[k][i]=f[f[k][i-1]][i-1];
    for(int i=0;i<g[k].size();++i)
    {
        if(g[k][i]==fa) continue;
        dfs(g[k][i],k);
    }
}
int LCA(int x,int y)
{
    if(d[x]<d[y]) swap(x,y);
    while(d[x]>d[y]) x=f[x][lg[d[x]-d[y]]-1];
    if(x==y) return x;
    for(int i=lg[d[x]]-1;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
void get(int k,int fa)
{
    for(int i=0;i<g[k].size();++i)
    {
        if(g[k][i]==fa) continue;
        get(g[k][i],k);
        sum[k]+=sum[g[k][i]];
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;++i)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;++i) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    dfs(1,0);
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        int lca=LCA(x,y);
        sum[x]++;
        sum[y]++;
        sum[lca]--;
        sum[f[lca][0]]--;
    }
    get(1,0);
    for(int i=1;i<=n;++i) ans=max(ans,sum[i]);
    cout<<ans;
    return 0;
}

树的重心

定义

对于树上的每一个点，计算其所有子树中最大的子树节点数，这个值最小的点就是这棵树的重心。

（这里以及下文中的“子树”都是指无根树的子树，即包括“向上”的那棵子树，并且不包括整棵树自身。）

性质

以树的重心为根时，所有子树的大小都不超过整棵树大小的一半。

树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么到它们的距离和一样。

把两棵树通过一条边相连得到一棵新的树，那么新的树的重心在连接原来两棵树的重心的路径上。

在一棵树上添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

求法

在 $\texttt{DFS}$ 中计算每个子树的大小，记录“向下”的子树的最大大小，利用总点数 - 当前子树（这里的子树指有根树的子树）的大小得到“向上”的子树的大小，然后就可以依据定义找到重心了。

例题

【模板】Balancing Act

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
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int inf=1e8;
vector<int> g[20002];
int t;
int n;
int x,y;
int ans1,ans2;
int siz[20002];
void dfs(int k,int fa)
{
    int maxs=-inf;
    for(int i=0;i<g[k].size();++i)
    {
        if(g[k][i]==fa) continue;
        dfs(g[k][i],k);
        siz[k]+=siz[g[k][i]]+1;
        maxs=max(maxs,siz[g[k][i]]+1);
    }
    maxs=max(maxs,n-siz[k]-1);
    if(maxs<ans2)
    {
        ans1=k;
        ans2=maxs;
    }
    else
    {
        if(maxs==ans2)
        {
            if(k<ans1)
            {
                ans1=k;
                ans2=maxs;
            }
        }
    }
}
void work()
{
    for(int i=0;i<=20000;++i) g[i].clear();
    memset(siz,0,sizeof(siz));
    ans1=0;
    ans2=inf;
    cin>>n;
    for(int i=1;i<n;++i)
    {
        cin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0);
    cout<<ans1<<" "<<ans2<<"\n";
}
int main()
{
    cin>>t;
    while(t--) work();
    return 0;
}

有一个引理：对于一颗以 $u$ 为根的子树，如果 $u$ 不是子树的重心，那么重心一定在 $u$ 的重儿子的子树里面。也就是说，如果 $u$ 不是自己的子树的重心，那么重心的方向我们是完全可以确定的。

于是可以考虑倍增优化，时间复杂度降为 $O(\log n)$。

[CSP-S2019] 树的重心

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
91
92
93
#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> g[300002];
int t;
int n;
int x,y;
int f[300002],F[300002];
int son[300002],son2[300002],son3[300002];
int so[300002][22];
int siz[300002],siz2[300002];
int ans;
inline int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
int sum(int k,int s)
{
    if(max(siz2[son3[k]],s-siz2[k])<=s/2) return k;
    return 0;
}
void dfs1(int k,int fa)
{
    siz[k]=1;
    f[k]=fa;
    for(int i=0;i<g[k].size();++i)
    {
        if(g[k][i]==fa) continue;
        dfs1(g[k][i],k);
        siz[k]+=siz[g[k][i]];
        if(siz[g[k][i]]>siz[son[k]]) son2[k]=son[k],son[k]=g[k][i];
            else if(siz[g[k][i]]>siz[son2[k]]) son2[k]=g[k][i];
    }
    so[k][0]=son[k];
    for(int i=1;i<=17;++i) so[k][i]=so[so[k][i-1]][i-1];
}
void dfs2(int k,int fa)
{
    for(int i=0;i<g[k].size();++i)
    {
        if(g[k][i]==fa) continue;
        siz2[k]=siz[1]-siz[g[k][i]];
        F[k]=0;F[g[k][i]]=0;
        if(son[k]==g[k][i]) son3[k]=son2[k];
            else son3[k]=son[k];
        if(siz2[fa]>siz2[son3[k]]) son3[k]=fa;
        so[k][0]=son3[k];
        for(int j=1;j<=17;++j) so[k][j]=so[so[k][j-1]][j-1];
        int l=k;
        for(int j=17;j>=0;--j) if(siz2[k]-siz2[so[l][j]]<=siz2[k]/2) l=so[l][j];
        ans+=sum(son3[l],siz2[k])+sum(l,siz2[k])+sum(F[l],siz2[k]);
        l=g[k][i];
        for(int j=17;j>=0;--j) if(siz2[g[k][i]]-siz2[so[l][j]]<=siz2[g[k][i]]/2) l=so[l][j];
        ans+=sum(son3[l],siz2[g[k][i]])+sum(l,siz2[g[k][i]])+sum(F[l],siz2[g[k][i]]);
        F[k]=g[k][i];
        dfs2(g[k][i],k);
    }
    son3[k]=so[k][0]=son[k];
    F[k]=f[k];
    siz2[k]=siz[k];
    for(int i=1;i<=17;++i) so[k][i]=so[so[k][i-1]][i-1];
}
void work()
{
    memset(f,0,sizeof(f));
    memset(son,0,sizeof(son));
    memset(son2,0,sizeof(son2));
    ans=0;
    for(int i=0;i<=300000;++i) g[i].clear();
    n=read();
    for(int i=1;i<n;++i)
    {
        x=read();y=read();
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(1,0);
    memcpy(siz2,siz,sizeof(siz2));
    memcpy(son3,son,sizeof(son3));
    memcpy(F,f,sizeof(F));
    dfs2(1,0);
    cout<<ans<<"\n";
}
signed main()
{
    cin>>t;
    while(t--) work();
    return 0;
}

总结

参考资料：

https://oi-wiki.org/graph/tree-diameter

https://oi-wiki.org/graph/lca

https://oi-wiki.org/graph/tree-centroid