前置
树的重心
树的直径、中心
LCA

前置

快读

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}

树的存储

通常我不喜欢什么儿子表示法父亲表示法。我通常直接链式前向星。

感觉还是很方便的。

#define N=100005;
int ver[N<<1],nxt[N<<1],head[N],tot,edge[N];
void add(int x,int y,int z)
{
    ver[++tot]=x,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
//搜索时
for(int i=head[x];i;i=nxt[i])
int y=ver[x];
//主函数中
for(int i=1;i<=n;i++)
{
int x=read(),y=read();
add(x,y),add(y,x);
}

树的搜索

通常喜欢直接DFS。

其中的边怎么弄就是链式前向星的基本操作了，感觉非常方便。

用参数$fa$判或者$vis$数组判都是可以的。

//a是DFS序,d是节点深度,s是子树大小
void dfs(int x)
{
    a[++m]=x,v[x]=1,s[x]=1;
    for(int i=head[x];i;i=next[i])
    {
        int y=ver[i];
        if(!v[y])
            d[y]=d[x]+1,dfs(y),s[x]+=s[y];
    }
    a[++m]=x;
}

P4914 二叉树深度

大概这个时候链式前向星的优势也就体现出来了。不需要什么繁琐的表示法，一个模板可以直接套到底。

const int SIZE=100005;
int nxt[SIZE<<1],ver[SIZE<<1],head[SIZE<<1],tot;
inline void add(int x,int y)
{
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
int n,dep[SIZE],ans;
void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y!=fa)dfs(y,x);
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read();
        if(x)add(i,x),add(x,i);
        if(y)add(i,y),add(y,i);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++)ans=max(ans,dep[i]);
    printf("%d\n",ans);
    return 0;
}

P1305 新二叉树

此题是先序遍历板题。

先序遍历：先根后左右
中序遍历：先左中根后右
后序遍历：先左右后根

注意链式前向星建图是后加的边先被搜索到，因此这里建树的时候需要先建右子树再建左子树。

const int SIZE=100005;
int nxt[SIZE<<1],ver[SIZE<<1],head[SIZE<<1],tot;
inline void add(int x,int y)
{
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
int n,rt;
void dfs(int x,int fa)
{
    printf("%c",x+'A');
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(y!=fa)dfs(y,x);
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        char x,y,z;cin>>x>>y>>z;
        int f=x-'A',l=y-'A',r=z-'A';
        if(z!='*')add(f,r),add(r,f);
        if(y!='*')add(f,l),add(l,f);
        if(i==1)rt=f;
    }
    dfs(rt,0);
    return 0;
}

树的重心

简单求解

一棵树的重心节点 $x$ 指的是：将 $x$ 从树中删除后，被分出的树中最大的部分最小。

因此我们任取一点为根，使用全局变量$mxpt$记录搜索到任意一点时，其最大子树的大小。然后对于每个节点，搜索结束后都更新$mxpt$。

void dfs(int x)
{
    v[x]=1,s[x]=val[x];
    int mxpt=0;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=ver[i];
        if(!v[y])
            dfs(y),s[x]+=s[y],
            mxpt=max(mxpt,s[y]);
    }
    mxpt=max(mxpt,sum-s[x]);
    if(mxpt
   
1
<p>
2
 <!-- /wp:enlighter/codeblock --></p>
3

4
<p>
5
 <!-- wp:heading {"level":3} --></p>
6

7
<h3>重心的性质</h3>
8

9
<p>
10
 <!-- /wp:heading --></p>
11

12
<p>
13
 <!-- wp:paragraph --></p>
14

15
<p>树的重心的一个显然的性质就是： <em>在边权为$1$时，以重心为根的树，各点到根节点的距离和最小</em> 。</p>
16

17
<p>
18
 <!-- /wp:paragraph --></p>
19

20
<p>
21
 <!-- wp:paragraph --></p>
22

23
<p><strong>证明</strong></p>
24

25
<p>
26
 <!-- /wp:paragraph --></p>
27

28
<p>
29
 <!-- wp:quote --></p>
30

31
<blockquote class="wp-block-quote">
32
 <p>使用邻项交换（微扰分析法）。</p>
33

34
 <p>假设我们已经求出了重心 $x$。设要到达的根为 $p$，不妨先令 $p=x$。现在使 $p$ 点向任意一条边 $w(p,q)$ 移动，发现造成距离和变化的唯一原因就是经过 $w(p,q)$ 到达点根的子节点数量发生了变化。</p>
35

36
 <p>因为重心保证了最大的一棵子树最小。因为移动先后的总节点数目是不变的，因此 $p$ 移动到 $w(p,q)$ 另一端 $q$ 后，$w(p,q)$ 指向的子树必然增大。这样就会导致通过 $w(p,q)$ 到达根的节点数增多，显然更劣。</p>
37

38
</blockquote>
39

40
<p>
41
 <!-- /wp:quote --></p>
42

43
<p>
44
 <!-- wp:paragraph --></p>
45

46
<p>有个板子题<a href="https://www.luogu.com.cn/problem/P1364">P1364 医院设置</a>。</p>
47

48
<p>
49
 <!-- /wp:paragraph --></p>
50

51
<p>
52
 <!-- wp:paragraph --></p>
53

54
<p>那么假如我们加了点权怎么办？</p>
55

56
<p>
57
 <!-- /wp:paragraph --></p>
58

59
<p>
60
 <!-- wp:paragraph --></p>
61

62
<p>其实是一样的，改一改 $size$ 即可。至于如何求解距离和，可以强制换根，一遍$DFS$搞定。</p>
63

64
<p>
65
 <!-- /wp:paragraph --></p>
66

67
<p>
68
 <!-- wp:paragraph --></p>
69

70
<p>题目：<a href="https://www.luogu.com.cn/problem/P1395">P1395 会议</a>。</p>
71

72
<p>
73
 <!-- /wp:paragraph --></p>
74

75
<p>
76
 <!-- wp:heading --></p>
77

78
<h2>带边权的重心</h2>
79

80
<p>
81
 <!-- /wp:heading --></p>
82

83
<p>
84
 <!-- wp:heading {"level":3} --></p>
85

86
<h3>模板：<a href="https://www.luogu.com.cn/problem/P2986">P2986 Great Cow Gathering</a></h3>
87

88
<p>
89
 <!-- /wp:heading --></p>
90

91
<p>
92
 <!-- wp:paragraph --></p>
93

94
<p>我们有个结论： <em>边权不影响树的重心</em> 。</p>
95

96
<p>
97
 <!-- /wp:paragraph --></p>
98

99
<p>
100
 <!-- wp:paragraph --></p>
101

102
<p>证明方法是类似的。</p>
103

104
<p>
105
 <!-- /wp:paragraph --></p>
106

107
<p>
108
 <!-- wp:paragraph --></p>
109

110
<p><strong>证明</strong></p>
111

112
<p>
113
 <!-- /wp:paragraph --></p>
114

115
<p>
116
 <!-- wp:quote --></p>
117

118
<blockquote class="wp-block-quote">
119
 <p>假设在边权为$1$的情况下我们找到了重心，那么以此为根其他的子树最大的一个最小。</p>
120

121
 <p>现在加了边权。假设这个重心往旁边移了，那么有影响的只是移过的那一条边。因为移动之后破坏了点权和最大值最小的性质，所以通过移动后的那条边的所有点权一定比移动之前大。</p>
122

123
</blockquote>
124

125
<p>
126
 <!-- /wp:quote --></p>
127

128
<p>
129
 <!-- wp:paragraph --></p>
130

131
<p>我们能否总结出一个规律？简单观察后发现，在根移动过后对距离和有影响的，只是移动过的那条边 <em>移动前后指向子树的大小</em> 以及 <em>本身的边权</em> 。根据重心的定义，以及边权是不变的，因此重心可以保证在任意边权和点权的时候保持原有性质。</p>
132

133
<p>
134
 <!-- /wp:paragraph --></p>
135

136
<p>
137
 <!-- wp:paragraph --></p>
138

139
<p>这题搜索的方法就是将深度由每次增加$1$变为增加边的长度。然后返回统计就是类似的。</p>
140

141
<p>
142
 <!-- /wp:paragraph --></p>
143

144
<p>
145
 <!-- wp:enlighter/codeblock --></p>
146

147
<pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">ll maxx(ll a,ll b){return a&gt;b?a:b;}

const ll SIZE=100005;
ll nxt[SIZE<<1],ver[SIZE<<1],head[SIZE<<1],val[SIZE<<1],tot;
inline void add(ll x,ll y,ll z)
{
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=z;
}
ll n,ans=10000000005,p,v[SIZE],s[SIZE],sum,w[SIZE];
void dfs(ll x)
{
v[x]=1,s[x]=w[x];
ll mxpt=0;
for(ll i=head[x];i;i=nxt[i])
{
ll y=ver[i];
if(!v[y])
dfs(y),s[x]+=s[y],
mxpt=maxx(mxpt,s[y]);
}
mxpt=maxx(mxpt,sum-s[x]);
if(mxpt
<ans)ans=mxpt,p=x; }="" void="" mvrt(ll="" x,ll="" fa,ll="" dep)="" {="" ans+=“w[x]*dep;” for(ll="" i=“1;i<n;i++)” ll="" y=“ver[i];” if(y!=“fa)mvrt(y,x,dep+val[i]);” int="" main()="" n=“read();” w[i]=“read(),sum+=w[i];” x=“read(),y=read(),z=read();” add(x,y,z),add(y,x,z);="" dfs(1),ans=“0,mvrt(p,-1,0);” printf(“%lld\n”,ans);="" return="" 0;="" }<="" re="">
1
  <p>
2
   <!-- /wp:enlighter/codeblock --></p>
3

4
  <p>
5
   <!-- wp:separator --></p>
6

7
  <hr class="wp-block-separator" />
8

9
  <!-- /wp:separator -->
10
  <p></p>
11

12
  <p>
13
   <!-- wp:heading {"level":1} --></p>
14

15
  <h1>树的直径、中心</h1>
16

17
  <p>
18
   <!-- /wp:heading --></p>
19

20
  <p>
21
   <!-- wp:heading --></p>
22

23
  <h2>树的直径</h2>
24

25
  <p>
26
   <!-- /wp:heading --></p>
27

28
  <p>
29
   <!-- wp:paragraph --></p>
30

31
  <p>一棵树上的最长链或最长链的长度称作这棵树的直径。</p>
32

33
  <p>
34
   <!-- /wp:paragraph --></p>
35

36
  <p>
37
   <!-- wp:paragraph --></p>
38

39
  <p>求解直径通常有三种方法。</p>
40

41
  <p>
42
   <!-- /wp:paragraph --></p>
43

44
  <p>
45
   <!-- wp:heading {"level":3} --></p>
46

47
  <h3>合并链法（树形dp）</h3>
48

49
  <p>
50
   <!-- /wp:heading --></p>
51

52
  <p>
53
   <!-- wp:paragraph --></p>
54

55
  <p>$dfs$ 找出每个节点下的最长链 $m_1$ 和次长链 $m_2$。</p>
56

57
  <p>
58
   <!-- /wp:paragraph --></p>
59

60
  <p>
61
   <!-- wp:paragraph --></p>
62

63
  <p>每次 $dfs$ 使 $ans$ 的值为最长和次长链的合并结果即可。</p>
64

65
  <p>
66
   <!-- /wp:paragraph --></p>
67

68
  <p>
69
   <!-- wp:enlighter/codeblock --></p>
70

71
  <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">int dp(int x,int fa)

{
int m1=0,m2=0;
for(int i=head[x];i;i=nxt[i])
{
int y=ver[i];
if(y!=fa)
{
int r=dp(y,x)+edge[i];
if(m1
<r)m2=m1,m1=r; else="" if(m2<r)m2=“r;” }="" ans=“max(m1+m2);” return="" m1;="" }<="" re="">
1
    <p>
2
     <!-- /wp:enlighter/codeblock --></p>
3

4
    <p>
5
     <!-- wp:paragraph --></p>
6

7
    <p>这种求法有另一种写法。</p>
8

9
    <p>
10
     <!-- /wp:paragraph --></p>
11

12
    <p>
13
     <!-- wp:paragraph --></p>
14

15
    <p>设 $d_x$ 为从 $x$ 出发走向以 $x$ 为根的子树的最远距离。我们可以通过此求出 $f_x$ 即经过 $x$ 的最长链长度。求解 $f_x$ 事实上就是合并最长链和次长链的过程。我们可以自底向上地统计结果。</p>
16

17
    <p>
18
     <!-- /wp:paragraph --></p>
19

20
    <p>
21
     <!-- wp:paragraph --></p>
22

23
    <p>当回溯到一个节点 $x$ 的时候，设其任意一个子节点为 $y$，我们直接将 $d_x$ 更新为 $\max\big(d_x,d_y+w(y,x)\big)$。这个转移的意义是，在搜索子节点的时候，将 <em>目前求出的最长链</em> 与其 <em>子节点 $y$ 的最长链加上 $w(y,x)$ 边</em> 这条候选的最长链作比较。</p>
24

25
    <p>
26
     <!-- /wp:paragraph --></p>
27

28
    <p>
29
     <!-- wp:paragraph --></p>
30

31
    <p>全局变量 $ans=\max\big(ans,x_x+d_y+w(y,x)\big)$，即是计算两条链的长度之和。</p>
32

33
    <p>
34
     <!-- /wp:paragraph --></p>
35

36
    <p>
37
     <!-- wp:enlighter/codeblock --></p>
38

39
    <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">void dp(int x)

{
v[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int y=ver[i];
if(!v[y])
{
dp(y);
ans=max(ans,d[x]+d[y]+edge[i]),
d[x]=max(d[x],d[y]+edge[i]);
}
}
}

1
    <p>
2
     <!-- /wp:enlighter/codeblock --></p>
3

4
    <p>
5
     <!-- wp:heading {"level":3} --></p>
6

7
    <h3>两次搜索</h3>
8

9
    <p>
10
     <!-- /wp:heading --></p>
11

12
    <p>
13
     <!-- wp:paragraph --></p>
14

15
    <p>使用两次搜索的方法能够求出直径的端点和直径的路径。</p>
16

17
    <p>
18
     <!-- /wp:paragraph --></p>
19

20
    <p>
21
     <!-- wp:paragraph --></p>
22

23
    <p>任取一个点 $x$，以 $x$ 为根寻找距离 $x$ 最远的点 $p$；然后以 $p$ 为根同样寻找到离 $p$ 最远的点 $q$，$p$ 和 $q$ 就是直径的两个端点。</p>
24

25
    <p>
26
     <!-- /wp:paragraph --></p>
27

28
    <p>
29
     <!-- wp:paragraph --></p>
30

31
    <p>记 $d_x$ 为到根的距离，简单搜索即可。</p>
32

33
    <p>
34
     <!-- /wp:paragraph --></p>
35

36
    <p>
37
     <!-- wp:paragraph --></p>
38

39
    <p><strong>正确性证明</strong></p>
40

41
    <p>
42
     <!-- /wp:paragraph --></p>
43

44
    <p>
45
     <!-- wp:quote --></p>
46

47
    <blockquote class="wp-block-quote">
48
     <p>$p$ 必然是直径的一端。如果不是，设另一点 $y$ 是直径的一段，因为求出的 $p$ 是距离 $x$ 最远的点，所以 $dis(p,x)&gt;dis(y,x)$。这与直径最长性矛盾，所以找不到符合要求的点 $y$，$p$ 是直径的一端。</p>
49

50
     <p>同理，$q$ 是距离直径的一端 $p$ 最远的点，自然就是直径的另一端。</p>
51

52
    </blockquote>
53

54
    <p>
55
     <!-- /wp:quote --></p>
56

57
    <p>
58
     <!-- wp:paragraph --></p>
59

60
    <p><strong>BFS求解</strong></p>
61

62
    <p>
63
     <!-- /wp:paragraph --></p>
64

65
    <p>
66
     <!-- wp:enlighter/codeblock --></p>
67

68
    <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">int bfs(int s)

{ int x,y; memset(d,0x3f,sizeof(d)); q.push(s),d[s]=0,pre[s]=0; while(q.size()) { x=q.front(),q.pop(); for(int i=head[x];i;i=next[i]) if(d[ver[i]]>=INF) d[ver[i]]=d[x]+edge[i], pre[ver[i]]=x, //记录前驱(路径) q.push(ver[i]); } for(x=1,y=1;x<=n;x++) if(d[x]>d[y])y=x; return y; }

//主函数中 p=bfs(1); q=bfs(p);

1
    <p>
2
     <!-- /wp:enlighter/codeblock --></p>
3

4
    <p>
5
     <!-- wp:paragraph --></p>
6

7
    <p><strong>DFS求解</strong></p>
8

9
    <p>
10
     <!-- /wp:paragraph --></p>
11

12
    <p>
13
     <!-- wp:enlighter/codeblock --></p>
14

15
    <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">int dfs(int x,int fa)

{ int pnt; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y!=fa) { d[y]=d[x]+edge[i],pre[y]=x; if(d[y]>d[pnt])pnt=y; dfs(y,x); } } return pnt; }

//主函数中 p=dfs(1,-1); memset(d,0x3f,sizeof(d)); q=dfs(p,-1);

1
    <p>
2
     <!-- /wp:enlighter/codeblock --></p>
3

4
    <p>
5
     <!-- wp:heading --></p>
6

7
    <h2>树的中心</h2>
8

9
    <p>
10
     <!-- /wp:heading --></p>
11

12
    <p>
13
     <!-- wp:paragraph --></p>
14

15
    <p>一棵树的中心 $x$ 满足，在树上所有的点中，到 $x$ 的最大距离最小。</p>
16

17
    <p>
18
     <!-- /wp:paragraph --></p>
19

20
    <p>
21
     <!-- wp:paragraph --></p>
22

23
    <p>$\color{black}{\mathbf{中心的性质及求法}}$</p>
24

25
    <p>
26
     <!-- /wp:paragraph --></p>
27

28
    <p>
29
     <!-- wp:paragraph --></p>
30

31
    <p>树的中心有一个很好的性质： <em>一棵树的中心是直径的中点</em> 。这里的中点是考虑边权的。</p>
32

33
    <p>
34
     <!-- /wp:paragraph --></p>
35

36
    <p>
37
     <!-- wp:paragraph --></p>
38

39
    <p><strong>简单证明</strong></p>
40

41
    <p>
42
     <!-- /wp:paragraph --></p>
43

44
    <p>
45
     <!-- wp:quote --></p>
46

47
    <blockquote class="wp-block-quote">
48
     <p>根据两次搜索的证明，我们已经知道距离任意一个点最远的点 $p$ 是直径的端点，而 $p$ 到达 $x$ 必然先经过直径的一段。</p>
49

50
     <p>假设路径 $(p,x)$ 拐出直径的点为 $y$，则我们先要最小化 $dis(p,y)+dis(x,y)$。因为 $dis(p,y)$ 在 $y$ 固定时是不变的，因此我们当然让 $dis(x,y)=0$，即 $x$ 在直径上。</p>
51

52
     <p>那么我们的 $y$ 点（即 $x$）如何选取？也就是使 $\max\big(dis(p,y),dis(q,y)\big)$ 最小，显然 $p$ 在直径的中点上。</p>
53

54
    </blockquote>
55

56
    <p>
57
     <!-- /wp:quote --></p>
58

59
    <p>
60
     <!-- wp:paragraph --></p>
61

62
    <p>证毕。</p>
63

64
    <p>
65
     <!-- /wp:paragraph --></p>
66

67
    <p>
68
     <!-- wp:paragraph --></p>
69

70
    <p>那么中心怎么求呢？</p>
71

72
    <p>
73
     <!-- /wp:paragraph --></p>
74

75
    <p>
76
     <!-- wp:paragraph --></p>
77

78
    <p>其实只需要这么一句话：</p>
79

80
    <p>
81
     <!-- /wp:paragraph --></p>
82

83
    <p>
84
     <!-- wp:enlighter/codeblock --></p>
85

86
    <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">for(int i=1;i&lt;=(d[q]+1)/2;i++)x=pre[x];</pre>
87

88
    <p>
89
     <!-- /wp:enlighter/codeblock --></p>
90

91
    <p>
92
     <!-- wp:paragraph --></p>
93

94
    <p>如果是带边权的话，我们可以记录 $pre$ 的同时记录边权，然后先求出直径长度，接着直径上每个点扫描过去，判断一下长度即可。</p>
95

96
    <p>
97
     <!-- /wp:paragraph --></p>
98

99
    <p>
100
     <!-- wp:heading --></p>
101

102
    <h2>直径、中心若干题目</h2>
103

104
    <p>
105
     <!-- /wp:heading --></p>
106

107
    <p>
108
     <!-- wp:heading {"level":3} --></p>
109

110
    <h3><a href="https://www.luogu.com.cn/problem/P4408">P4408 逃学的小孩</a></h3>
111

112
    <p>
113
     <!-- /wp:heading --></p>
114

115
    <p>
116
     <!-- wp:paragraph --></p>
117

118
    <p>找直径没有问题罢。</p>
119

120
    <p>
121
     <!-- /wp:paragraph --></p>
122

123
    <p>
124
     <!-- wp:paragraph --></p>
125

126
    <p>找完之后我们枚举直径外其他的点，这些点和俩端点形成类似于一个三角形的东西。</p>
127

128
    <p>
129
     <!-- /wp:paragraph --></p>
130

131
    <p>
132
     <!-- wp:paragraph --></p>
133

134
    <p>然后直径这条边是必须选的，剩下两条边要考虑走哪条边。题目告诉你先走近的，所以剩下俩边选取短的那条就行了。</p>
135

136
    <p>
137
     <!-- /wp:paragraph --></p>
138

139
    <p>
140
     <!-- wp:paragraph --></p>
141

142
    <p>然后这些点都枚举完之后取最大值即可。</p>
143

144
    <p>
145
     <!-- /wp:paragraph --></p>
146

147
    <p>
148
     <!-- wp:heading {"level":3} --></p>
149

150
    <h3><a href="https://www.luogu.com.cn/problem/P5536">P5536 核心城市</a></h3>
151

152
    <p>
153
     <!-- /wp:heading --></p>
154

155
    <p>
156
     <!-- wp:paragraph --></p>
157

158
    <p>根据中心的定义，首先可以明确的是选取的城市必然包含中心。</p>
159

160
    <p>
161
     <!-- /wp:paragraph --></p>
162

163
    <p>
164
     <!-- wp:paragraph --></p>
165

166
    <p>于是我们以中心为根，设 $D_x$ 表示从 $x$ 出发走向以 $x$ 为根的子树的最远距离。我们每次选一个城市的时候，因为要保证最大值最小，所以肯定是先选择剩下城市中 $D_x$ 最大的。因此这样下去，最终选择的是 $D_x$ 前 $k$ 大的。</p>
167

168
    <p>
169
     <!-- /wp:paragraph --></p>
170

171
    <p>
172
     <!-- wp:paragraph --></p>
173

174
    <p>所以我们只需$DFS$求出 $D_x$，然后排序即可。</p>
175

176
    <p>
177
     <!-- /wp:paragraph --></p>
178

179
    <p>
180
     <!-- wp:enlighter/codeblock --></p>
181

182
    <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">bool cmp(int a,int b){return a&gt;b;}

const int SIZE=200010; int nxt[SIZE],ver[SIZE],head[SIZE],tot; inline void add(int x,int y) { ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; } int d[SIZE],pre[SIZE],dpx[SIZE],jed[SIZE]; int n,k,maxd,p,q,ans,t; void dfs1(int x,int fa) { if(d[x]>maxd)maxd=d[x],p=x; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y!=fa) d[y]=d[x]+1, dfs1(y,x); } } void dfs2(int x,int fa) { if(d[x]>maxd)maxd=d[x],q=x; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y!=fa) d[y]=d[x]+1, pre[y]=x,dfs2(y,x); } } void dfs3(int x,int fa) { dpx[x]=d[x]; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y!=fa) d[y]=d[x]+1,dfs3(y,x), dpx[x]=max(dpx[x],dpx[y]); } } int main() { n=read(),k=read(); for(int i=1;i <n;i++) {="" int="" x=“read(),y=read();” add(x,y),add(y,x);="" }="" dfs1(1,-1);="" memset(dp,0,sizeof(dp));="" maxd=“0,dfs2(p,-1),t=q;” for(int="" i=“k+1;i<=n;i++)” t=“pre[t];” dfs3(t,0);="" jed[i]=“dpx[i]-d[i];” sort(jed+1,jed+n+1,cmp);="" ans=“max(ans,jed[i]+1);” printf(“%d\n”,ans);="" return="" 0;="" }<="" re="">

1
      <p>
2
       <!-- /wp:enlighter/codeblock --></p>
3

4
      <p>
5
       <!-- wp:heading {"level":3} --></p>
6

7
      <h3><a href="https://www.luogu.com.cn/problem/P2195">P4914 HXY造公园</a></h3>
8

9
      <p>
10
       <!-- /wp:heading --></p>
11

12
      <p>
13
       <!-- wp:paragraph --></p>
14

15
      <p>用并查集维护森林，然后每次合并两棵树就连接其中心，更新即可。</p>
16

17
      <p>
18
       <!-- /wp:paragraph --></p>
19

20
      <p>
21
       <!-- wp:paragraph --></p>
22

23
      <p>具体而言，我们建立数组 $C$ 表示每个集合的最长路径。合并集合的时候，定义 $tmp$ 为连接两个中心后的最长距离，当合并集合 $x,y$ 时，显而易见</p>
24

25
      <p>
26
       <!-- /wp:paragraph --></p>
27

28
      <p>
29
       <!-- wp:paragraph --></p>
30

31
      <p>$$tmp=\max\left(C_x\,,\;\Big\lfloor\frac{C_x}{2}\Big\rfloor+\Big\lfloor\frac{C_y}{2}\Big\rfloor+1\,,\;C_y\right)$$</p>
32

33
      <p>
34
       <!-- /wp:paragraph --></p>
35

36
      <p>
37
       <!-- wp:paragraph --></p>
38

39
      <p>因此我们用并查集合并集合，并且用 $tmp$ 去更新 $C$ 即可。</p>
40

41
      <p>
42
       <!-- /wp:paragraph --></p>
43

44
      <p>
45
       <!-- wp:enlighter/codeblock --></p>
46

47
      <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">const int SIZE=300005;

int nxt[SIZE<<1],ver[SIZE<<1],head[SIZE<<1],tot; inline void add(int x,int y) { ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; } int d[SIZE],g[SIZE],f[SIZE],c[SIZE],n,m,q,len; bool vis[SIZE]; inline int find(int x) { if(f[x]==x)return x; return f[x]=find(f[x]); } void dfs(int x,int fa) { int m1=0,m2=0,tmp; for(int i=head[x];i;i=nxt[i]) { int y=ver[i]; if(y!=fa) { dfs(y,x),tmp=d[y]+1; d[x]=max(d[x],tmp); if(tmp>m1)m2=m1,m1=tmp; else if(tmp>m2)m2=tmp; } } g[x]=max(max(0,m1+m2),max(m1,m2)); len=max(len,g[x]); } int main(){ n=read(),m=read(),q=read(); for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=m;i++) { int x=read(),y=read(); f[find(x)]=find(y); add(x,y),add(y,x); } for(int i=1;i<=n;i++) if(f[i]==i&&(!vis[i])) { len=0,dfs(i,0); c[i]=len,vis[i]=1; } while(q—) { int opt=read(),x=read(); if(opt==1) { printf(“%d\n”,c[find(x)]); continue; } int y=read(); x=find(x),y=find(y); if(x!=y) { int tmp=ceil(c[x]/2.0)+ceil(c[y]/2.0)+1; tmp=max(tmp,max(c[x],c[y])); f[find(x)]=find(y); c[find(x)]=tmp; } } return 0; }

1
      <p>
2
       <!-- /wp:enlighter/codeblock --></p>
3

4
      <p>
5
       <!-- wp:heading {"level":3} --></p>
6

7
      <h3><a href="https://www.luogu.com.cn/problem/P1099">P1099 树网的核</a></h3>
8

9
      <p>
10
       <!-- /wp:heading --></p>
11

12
      <p>
13
       <!-- wp:paragraph --></p>
14

15
      <p>先找直径。</p>
16

17
      <p>
18
       <!-- /wp:paragraph --></p>
19

20
      <p>
21
       <!-- wp:paragraph --></p>
22

23
      <p>我们先确定一个端点，核的另一端点显然越远越好，所以直接确定那个点然后遍历树即可，复杂度二次。</p>
24

25
      <p>
26
       <!-- /wp:paragraph --></p>
27

28
      <p>
29
       <!-- wp:paragraph --></p>
30

31
      <p>联想到树的中心，我们能够容易地证明，核的端点越靠近树的中心越好，因此我们从中心出发向外找两个点让它最远。</p>
32

33
      <p>
34
       <!-- /wp:paragraph --></p>
35

36
      <p>
37
       <!-- wp:paragraph --></p>
38

39
      <p>因此我们略作转化。设 $p,q$ 为直径的两端，二分判定一个偏心距，求出这个偏心距的最短的核，然后判定这个偏心距的核满不满足条件。具体来说，我们判定偏心距 $mid$，从 $p,q$ 分别在直径上找到距离小于等于 $mid$ 的最远的两点，然后判定这两个点是否过长即可。正确性由直径最长性保证。</p>
40

41
      <p>
42
       <!-- /wp:paragraph --></p>
43

44
      <p>
45
       <!-- wp:paragraph --></p>
46

47
      <p>然而你会发现上述做法纯属多余。我们为什么不能直接 $DFS$ 处理出不经过直径上的其他点能到达的最远距离 $D_x$ 呢？</p>
48

49
      <p>
50
       <!-- /wp:paragraph --></p>
51

52
      <p>
53
       <!-- wp:paragraph --></p>
54

55
      <p>计直径上的节点为 $u_k(0
56
       <k\leq t)$，单调队列维护="" $i,j$，求下式最小值<="">
57

58
       </k\leq></p>
59
      <p>
60
       <!-- /wp:paragraph --></p>
61

62
      <p>
63
       <!-- wp:paragraph --></p>
64

65
      <p>$$\max\left(\max_{i\leq k\leq j}{d_{u_i}},dis(u_1,u_i),dis(u_j,u_t)\right)$$</p>
66

67
      <p>
68
       <!-- /wp:paragraph --></p>
69

70
      <p>
71
       <!-- wp:paragraph --></p>
72

73
      <p>复杂度降为 $O(n)$。</p>
74

75
      <p>
76
       <!-- /wp:paragraph --></p>
77

78
      <p>
79
       <!-- wp:paragraph --></p>
80

81
      <p>进一步，根据直径的最长性，$i,j$ 两点上的 $D$ 数组的值是不会大于 $dis(u_1,u_i)$ 或 $dis(u_j,u_t)$ 的；并且，在 $kj$ 的时候，$D_k$ 也不会大于$dis(u_1,u_i)$ 或 $dis(u_j,u_t)$。因此，真正对 $\max$ 做贡献 $D_k$ 的只是 $i
82
       <k<j$ 的部分。<="">
83

84
       </k<j$></p>
85
      <p>
86
       <!-- /wp:paragraph --></p>
87

88
      <p>
89
       <!-- wp:paragraph --></p>
90

91
      <p>这表示我们可以随意扩大 $\max$ 下方的范围！也就是说，我们完全可以将式子变为下面这个样子而不改变正确性，从而内部的那个 $max$ 函数的结果成为了定值，也就不需要单调队列了：</p>
92

93
      <p>
94
       <!-- /wp:paragraph --></p>
95

96
      <p>
97
       <!-- wp:paragraph --></p>
98

99
      <p>$$\max\left(\max_{1\leq k\leq t}{d_{u_i}},dis(u_1,u_i),dis(u_j,u_t)\right)$$</p>
100

101
      <p>
102
       <!-- /wp:paragraph --></p>
103

104
      <p>
105
       <!-- wp:paragraph --></p>
106

107
      <p>至此，这道题的最简解法也就明晰了。</p>
108

109
      <p>
110
       <!-- /wp:paragraph --></p>
111

112
      <p>
113
       <!-- wp:heading {"level":3} --></p>
114

115
      <h3><a href="https://www.luogu.com.cn/problem/P2491">P2491 消防</a></h3>
116

117
      <p>
118
       <!-- /wp:heading --></p>
119

120
      <p>
121
       <!-- wp:paragraph --></p>
122

123
      <p>这题是树网的核的双倍经验，除了证明选点在直径上之外，是完全一样了。</p>
124

125
      <p>
126
       <!-- /wp:paragraph --></p>
127

128
      <p>
129
       <!-- wp:paragraph --></p>
130

131
      <p>链在直径上的证明基本只是用到了最长性，很好证，不赘述了。</p>
132

133
      <p>
134
       <!-- /wp:paragraph --></p>
135

136
      <p>
137
       <!-- wp:heading {"level":3} --></p>
138

139
      <h3><a href="https://www.luogu.com.cn/problem/P3629">P3629 巡逻</a></h3>
140

141
      <p>
142
       <!-- /wp:heading --></p>
143

144
      <p>
145
       <!-- wp:paragraph --></p>
146

147
      <p>首先不加边的话，显然每条边走过两次。</p>
148

149
      <p>
150
       <!-- /wp:paragraph --></p>
151

152
      <p>
153
       <!-- wp:paragraph --></p>
154

155
      <p>可以发现的是，在树中加入一条边后，会形成一个环。这个环上的所有点都只需要走过一次，比原先的两次减少了一次。</p>
156

157
      <p>
158
       <!-- /wp:paragraph --></p>
159

160
      <p>
161
       <!-- wp:paragraph --></p>
162

163
      <p>所以当 $k=1$ 时，我们显然找直径，这样可以最大化环的大小。设直径长度 $l$，总边数 $x$，则最终答案为 $2x-l+1$。</p>
164

165
      <p>
166
       <!-- /wp:paragraph --></p>
167

168
      <p>
169
       <!-- wp:paragraph --></p>
170

171
      <p>当 $k=2$ 时，我们的第二条边与第一条边所形成的环的重叠边会需要走两次（画图理解），这样这部分就等于没有变化。因此我们在直径的基础上，需要让重叠部分小、不重叠部分多。</p>
172

173
      <p>
174
       <!-- /wp:paragraph --></p>
175

176
      <p>
177
       <!-- wp:paragraph --></p>
178

179
      <p>这两个要素没有优先级之分，但是我们注意到，对于缩小走的边数而言，不重叠部分的边贡献为 $1$，重叠的边贡献为 $-1$，我们要最大化贡献和。所以我们可以将第一条直径上的边赋值为 $-1$，其余赋值为 $1$，再找一次直径。这样我们得出的第二条直径就是能够最大化贡献的第二个环（当然这个环包含了端点之间的边）。</p>
180

181
      <p>
182
       <!-- /wp:paragraph --></p>
183

184
      <p>
185
       <!-- wp:paragraph --></p>
186

187
      <p>于是当 $k=2$ 时，设第一条直径长度为 $l_1$，第二条为 $l_2$，原边数为 $x$，则最终答案为 $2x-l_1-l_2+2$。</p>
188

189
      <p>
190
       <!-- /wp:paragraph --></p>
191

192
      <p>
193
       <!-- wp:separator --></p>
194

195
      <hr class="wp-block-separator" />
196

197
      <!-- /wp:separator -->
198
      <p></p>
199

200
      <p>
201
       <!-- wp:heading {"level":1} --></p>
202

203
      <h1>最近公共祖先 $\text{LCA}$</h1>
204

205
      <p>
206
       <!-- /wp:heading --></p>
207

208
      <p>
209
       <!-- wp:paragraph --></p>
210

211
      <p>朴素方法就是两个点先移到同样的深度，然后一条边一条边向上移。这种方法单次求就达到了线性的复杂度，不能处理较大数据。</p>
212

213
      <p>
214
       <!-- /wp:paragraph --></p>
215

216
      <p>
217
       <!-- wp:paragraph --></p>
218

219
      <p>我们能否再低于线性的复杂度内求得 $LCA$？当然是可以的，使用 <em>倍增算法</em>。</p>
220

221
      <p>
222
       <!-- /wp:paragraph --></p>
223

224
      <p>
225
       <!-- wp:paragraph --></p>
226

227
      <p>我们定义 $f[i][j]$ 表示节点 $i$ 的上 $2^j$ 级祖先。我们可以先一遍 $dfs$ 预处理出相关信息。</p>
228

229
      <p>
230
       <!-- /wp:paragraph --></p>
231

232
      <p>
233
       <!-- wp:enlighter/codeblock --></p>
234

235
      <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">void dfs(int x,int fa)

{ f[x][0]=fa,d[x]=d[fa]+1; for(int i=1;i<=lg[d[x]];i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=head[x];i;i=nxt[i]) if(ver[i]!=fa)dfs(ver[i],x); }

1
      <p>
2
       <!-- /wp:enlighter/codeblock --></p>
3

4
      <p>
5
       <!-- wp:paragraph --></p>
6

7
      <p>于是我们用树上倍增求出 $x,y$ 的最近公共祖先，具体而言：</p>
8

9
      <p>
10
       <!-- /wp:paragraph --></p>
11

12
      <p>
13
       <!-- wp:list {"ordered":true} --></p>
14

15
      <ol>
16

17
       <li>将点的深度调节一致；</li>
18

19
       <li>将 $x,y$ 树上倍增上移至 $f[x][0]=f[y][0]$。</li>
20

21
      </ol>
22

23
      <p>
24
       <!-- /wp:list --></p>
25

26
      <p>
27
       <!-- wp:paragraph --></p>
28

29
      <p>然后 $f[x][0]$ 即为所求。</p>
30

31
      <p>
32
       <!-- /wp:paragraph --></p>
33

34
      <p>
35
       <!-- wp:enlighter/codeblock --></p>
36

37
      <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">//树上倍增

inline 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 k=lg[d[x]]-1;k>=0;k—) if(f[x][k]!=f[y][k]) x=f[x][k],y=f[y][k]; return f[x][0]; }

//主函数中 for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1< <lg[i-1]==i); d[1]=“1,dfs(1,1);” for(int="" i=“1;i<=m;i++)” {="" int="" x=“read(),y=read();” printf(“%d\n”,lca(x,y));="" }<="" re="">

1
         <p>
2
          <!-- /wp:enlighter/codeblock --></p>
3

4
         <p>
5
          <!-- wp:heading --></p>
6

7
         <h2>$\text{LCA}$ 的应用</h2>
8

9
         <p>
10
          <!-- /wp:heading --></p>
11

12
         <p>
13
          <!-- wp:heading {"level":3} --></p>
14

15
         <h3><a href="https://www.luogu.com.cn/problem/P3398">P3398 仓鼠找sugar</a></h3>
16

17
         <p>
18
          <!-- /wp:heading --></p>
19

20
         <p>
21
          <!-- wp:paragraph --></p>
22

23
         <p>判断 $(a,b),(c,d)$ 两条路径是否相交。</p>
24

25
         <p>
26
          <!-- /wp:paragraph --></p>
27

28
         <p>
29
          <!-- wp:paragraph --></p>
30

31
         <p>有个非常显然的结论就是，当 $LCA(a,b)$ 在路径 $(c,d)$ 上或 $LCA(c,d)$ 在路径 $(a,b)$ 时就是相交的。</p>
32

33
         <p>
34
          <!-- /wp:paragraph --></p>
35

36
         <p>
37
          <!-- wp:quote --></p>
38

39
         <blockquote class="wp-block-quote">
40
          <p>这是因为每个节点的父亲是唯一的。所以如果相交的话，必然会有一个点同时在两条路径上，而且是其中一条的公共祖先。否则若所有相交的点都不是 $LCA$，那么至少会出现一个点有两个父亲，这不符合树的定义。</p>
41

42
         </blockquote>
43

44
         <p>
45
          <!-- /wp:quote --></p>
46

47
         <p>
48
          <!-- wp:paragraph --></p>
49

50
         <p>上面只是一个粗略的证明，详细内容就不写了，感性理解一下。</p>
51

52
         <p>
53
          <!-- /wp:paragraph --></p>
54

55
         <p>
56
          <!-- wp:paragraph --></p>
57

58
         <p>于是我们判断深度较大的 $LCA$ 是否在另一条的路径上即可。</p>
59

60
         <p>
61
          <!-- /wp:paragraph --></p>
62

63
         <p>
64
          <!-- wp:heading {"level":3} --></p>
65

66
         <h3><a href="https://www.luogu.com.cn/problem/P4281">P4281 紧急集合</a></h3>
67

68
         <p>
69
          <!-- /wp:heading --></p>
70

71
         <p>
72
          <!-- wp:paragraph --></p>
73

74
         <p>因为树上的最短路径是唯一的，所以我们不妨先求出三个点的 $LCA$。</p>
75

76
         <p>
77
          <!-- /wp:paragraph --></p>
78

79
         <p>
80
          <!-- wp:paragraph --></p>
81

82
         <p>设三个点的 $LCA$ 分别为 $x,y,z$，经过简单的思考，我们不难得出以下两个结论：</p>
83

84
         <p>
85
          <!-- /wp:paragraph --></p>
86

87
         <p>
88
          <!-- wp:list {"ordered":true} --></p>
89

90
         <ol>
91

92
          <li>这三个点最多会在两个不同的位置；</li>
93

94
          <li>集合点选取在两两重合的 $LCA$ 处比单独的 $LCA$ 处更优。</li>
95

96
         </ol>
97

98
         <p>
99
          <!-- /wp:list --></p>
100

101
         <p>
102
          <!-- wp:paragraph --></p>
103

104
         <p>直接找到即可。</p>
105

106
         <p>
107
          <!-- /wp:paragraph --></p>
108

109
         <p>
110
          <!-- wp:paragraph --></p>
111

112
         <p><strong>证明</strong></p>
113

114
         <p>
115
          <!-- /wp:paragraph --></p>
116

117
         <p>
118
          <!-- wp:quote --></p>
119

120
         <blockquote class="wp-block-quote">
121
          <p>对于第一个结论，我们先在树上选取 $LCA$，然后证明至少有两个点要选在同一个位置。</p>
122

123
          <p>计以第一次选取的点 $x$ 为共同祖先的两条路径为 $U_1,V_1$。当我们选取第二个点 $y$ 作为 $LCA$ 的时候，我们必须要让它的两条路径 $U_2,V_2$ 中的一条经过 $x$，且覆盖其中一条路径的全部。这是因为如果不经过 $x$，则会有一个点出现两个父亲；而如果不覆盖全部路径的话，会除了 $x$ 和 $y$ 之外会出现四个端点，这与题目中的三个点不符。</p>
124

125
          <p>关于第二个结论，证明类似树的重心，故不放出了。</p>
126

127
         </blockquote>
128

129
         <p>
130
          <!-- /wp:quote --></p>
131

132
         <p>
133
          <!-- wp:heading {"level":3} --></p>
134

135
         <h3><a href="https://www.luogu.com.cn/problem/P1967">P1967 货车运输</a></h3>
136

137
         <p>
138
          <!-- /wp:heading --></p>
139

140
         <p>
141
          <!-- wp:paragraph --></p>
142

143
         <p>在原图上构建最大生成树，然后在生成树上跑 $LCA$ 求解。</p>
144

145
         <p>
146
          <!-- /wp:paragraph --></p>
147

148
         <p>
149
          <!-- wp:enlighter/codeblock --></p>
150

151
         <pre class="EnlighterJSRAW" data-enlighter-language="generic" data-enlighter-theme="" data-enlighter-highlight="" data-enlighter-linenumbers="" data-enlighter-lineoffset="" data-enlighter-title="" data-enlighter-group="">const int SIZE=100005;

const int INF=99999999; int ver[SIZE],nxt[SIZE],val[SIZE],tot,head[SIZE]; void add(int x,int y,int z) { nxt[++tot]=head[x],ver[tot]=y,val[tot]=z,head[x]=tot; } struct node{int u,v,w;}a[SIZE]; int n,m,d[SIZE],f[SIZE],fat[SIZE][50],dp[SIZE][50],q,v[SIZE]; bool cmp(node x,node y){return x.w>y.w;} int find(int x) { if(f[x]==x)return x; return f[x]=find(f[x]); } void dfs(int x) { v[x]=1; for(int i=head[x];i;i=nxt[i]) { int y=ver[i],z=val[i]; if(!v[y]) d[y]=d[x]+1,fat[y][0]=x, dp[y][0]=z,dfs(y); } } int LCA(int x,int y) { if(find(x)!=find(y))return -1; int ans=INF; if(d[x]>d[y])swap(x,y); for(int i=25;i>=0;i—) if(d[fat[y][i]]>=d[x]) ans=min(ans,dp[y][i]),y=fat[y][i]; if(x==y)return ans; for(int i=25;i>=0;i—) if(fat[x][i]!=fat[y][i]) ans=min(ans,min(dp[x][i],dp[y][i])), x=fat[x][i],y=fat[y][i]; ans=min(ans,min(dp[x][0],dp[y][0])); return ans; } void kruskal() { sort(a+1,a+m+1,cmp); for(int i=1;i<=n;i++)f[i]=i; for(int i=1;i<=m;i++) if(find(a[i].u)!=find(a[i].v)) { f[find(a[i].u)]=find(a[i].v); add(a[i].u,a[i].v,a[i].w); add(a[i].v,a[i].u,a[i].w); } } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); a[i].u=x,a[i].v=y,a[i].w=z; } kruskal(); for(int i=1;i<=n;i++) if(!v[i]) d[i]=1,dfs(i), fat[i][0]=i,dp[i][0]=INF; for(int i=1;i<=25;i++) for(int j=1;j<=n;j++) fat[j][i]=fat[fat[j][i-1]][i-1], dp[j][i]=min(dp[j][i-1],dp[fat[j][i-1]][i-1]); q=read(); for(int i=1;i<=q;i++) { int x=read(),y=read(); printf(“%d\n”,LCA(x,y)); } return 0; }

1
         <p>
2
          <!-- /wp:enlighter/codeblock --></p>
3

4
         <p>
5
          <!-- wp:paragraph --></p>
6

7
         <p>
8
          <!-- /wp:paragraph --></p>
9

10
        </lg[i-1]==i);>
11
       </d[y])swap(x,y);></pre>
12
     </n;i++)></pre>
13
   </r)m2=m1,m1=r;></pre>
14
 </ans)ans=mxpt,p=x;></pre>

</ans)ans=mxpt,p=x;>

前置

快读

树的存储

树的搜索

P4914 二叉树深度

P1305 新二叉树

树的重心

简单求解

支持与分享

评论区

目录

树上问题总结（一）

前置

快读

树的存储

树的搜索

P4914 二叉树深度

P1305 新二叉树

树的重心

简单求解

支持与分享

评论区

目录