洛谷题库 P3304 [SDOI2013]直径 题解与思路重现

洛谷题库 P3304 [SDOI2013]直径

想看正解请直接跳过文章前半段。

不知道到底错没错的错解

这是一道树的直径的必经边问题。

单单求树的直径是非常简单的。可以通过两次DFS/BFS或一次树形DP完成$\mathrm{O}(N)$的求解。显然，树的直径长度唯一，但构成该长度的链的方案可能不唯一。

一开始，我想通过两次树形DP完成求解：假设我们已求出直径长为$D$。设$f[x]\{mx, mxcnt\}$记录在以$1$号节点作根时节点$x$的子树上的最大深度及其计数（深度最大的链可能不止一条），显然有$$f[x] = \begin{cases}f[son_i] & f[son_i].mx > f[x].mx \\ \{f[x].mx, f[x].mxcnt + f[son_i].mxcnt\} & f[son_i].mx = f[x].mx \end{cases}$$进而通过换根DP求出$F[x]\{mx, mxcnt\}$，即在以$x$为整棵树的根时的最大深度和计数（求解方法类似于$f[x]$）。求解$F[x]$时，$x$的父亲节点$fa$的$F[fa]$应当已经求出，这时如果边$x \leftrightarrow fa$在直径上，则有$f[x].mx + F[fa].mx = D$，且通过该边的直径条数应该是$cnt = f[x].mxcnt \times F[x].mxcnt$。如果它是一条必经边，则有$cnt \geq maxcnt$，其中$maxcnt$是全局中$cnt$的最大值。若有$cnt \ge maxcnt$，则说明“$cnt$才是直径条数”，$ans$重置为$1$；若有$cnt = maxcnt$，则$ans$自增$1$。

乍看，这个方法好像很有道理。正准备实现的时候，再一细想却傻眼了：

1. 如果$F[fa]$在转移时采取的是包含$x$的方案（即以$fa$作根时，最大深度的那条链恰好包含现在扫描到的$x$），怎么办？
2. 在菊花图上使用该方法，您将顺利得到所有的边都是直径必经边的错误结果。

对于第一个问题，我曾考虑过记录次大的$F[x]$和$f[x]$，转移时保证采取的$F[x]$不包含当前所在链的方案。但是实现起来太太太复杂了……还非常容易写错。至于为什么会出现第二个问题……请看下面的菊花图。

一个根节点度为3的菊花图

显然，该图共有3条直径$2 \leftrightarrow 1 \leftrightarrow 4$、$2 \leftrightarrow 1 \leftrightarrow 3$和$3 \leftrightarrow 1 \leftrightarrow 4$，且必经边条数为$0$。采取如上方法计算，会得到$cnt_2 = cnt_3 = cnt_4 = maxcnt = 3$，导致三条边全部计入答案。

所以这个花了我两个晚自习加一个小时的方法报废了。

正解

在说明正解之前，需要捣鼓几条推论。

引理 1

若树的直径方案不唯一，则设一条直径的点集为$V_a$，另一条直径的点集为$V_b$，有$V_a \cap V_b \neq \emptyset$。

采用反证法证明。假设有$V_a \cap V_b = \emptyset$。设两条直径两端点分别为$x_{a1}, x_{a2}$和$x_{b1}, x_{b2}$，则由树上两点之间有且仅有一条简单路径可知，必然存在路径$x_{a3} \longleftrightarrow x_{b3} \space (x_{a3} \in V_a, x_{b3} \in V_b)$，使得两直径上任意两点相互可达。在两条直径上，$x_{a1}, x_{a2}$和$x_{a3}$的距离、$x_{b1}, x_{b2}$和$x_{b3}$的距离分别记作$\mathrm{dis}(x_{a1}, x_{a3})$，$\mathrm{dis}(x_{a2}, x_{a3})$，$\mathrm{dis}(x_{b1}, x_{b3})$和$\mathrm{dis}(x_{b2}, x_{b3})$。容易知道，有$\max(\mathrm{dis}(x_{a1}, x_{a3}), \mathrm{dis}(x_{a2}, x_{a3})) \geq D/2$，$\max(\mathrm{dis}(x_{b1}, x_{b3}), \mathrm{dis}(x_{b2}, x_{b3})) \geq D/2$。则取$$\max(\mathrm{dis}(x_{a1}, x_{a3}), \mathrm{dis}(x_{a2}, x_{a3})) + \max(\mathrm{dis}(x_{b1}, x_{b3}), \mathrm{dis}(x_{b2}, x_{b3})) + \mathrm{dis}(x_{a3}, x_{b3}) \geq D$$，当且仅当$$\mathrm{dis}(x_{a3}, x_{b3}) = 0 \land \max(\mathrm{dis}(x_{b1}, x_{b3}), \mathrm{dis}(x_{b2}, x_{b3})) = \max(\mathrm{dis}(x_{a1}, x_{a3}), \mathrm{dis}(x_{a2}, x_{a3})) = D/2$$时等号成立，此时$x_{a3}$与$x_{b3}$代表的点相同（这其实是一张特殊的菊花图）。此时$x_{a3}, x_{b3} \in V_a \cap V_b$，与假设相矛盾，故不成立。

由此，我们可以推广到多条直径的情况，结论就是：对于多条由点集$V_1, V_2, \dots, V_n$构成的直径，必然有$\bigcap\limits_{i=1}^n V_i \neq \emptyset$。

引理 2

设有$n$条直径长度为$D$，共用长度为$L$的路径，各条直径上$L$一侧的长度为$S_1, S_2, \dots, S_n$，则有$S_1 = S_2 = \dots = S_n$。

这也很容易证明。我们先只考虑有两条直径的情况。假设$S_1 \neq S_2$，且$S_1 > S_2$，即第一条直径的左侧更长一些。则在两条直径共用路径的另一端，其长度为$D-L-S2 > D- L-S1$，即第二条直径的右端更长一些。则我们拼接第一条直径的左端、共用路径和第二条直径的右端，得到一条长度为$S_1 + L + D-L-S_2 = S_1-S_2 + D > D$的新路径，与直径的定义矛盾，假设不成立。显然，这可以推广到有更多直径的情况。

假设我们已经通过某种方式求出了一条直径上的节点，有没有办法求出这棵树一共有多少条直径呢？

考虑节点$x \in L$，即在所有直径的共用路径上。我们考虑从已知直径的右端点、左端点作根（把直径的两端分别吊起来），分别求出根的两个位置下$x$的子树的最大深度以及最大深度计数，记作$dep[x][0]\{mx, mxcnt\}, dep[x][1]\{mx, mxcnt\}$。显然有$dep[x][0].mx + dep[x][1].mx = D$，否则与直径的定义相悖。此时，最大深度计数就代表着从$x$向左走和向右走，分别有多少条最长路可以选择。根据乘法原理，直径总数就是两侧方案数相乘，即 $D\_cnt = dep[x][0].mxcnt \times dep[x][1].mxcnt$。

所以，若是某条边处于必经边上，则其两端节点 $x_1, x_2$ 之 $$dep[x_1][0].mxcnt \times dep[x_1][1].mxcnt = dep[x_2][0].mxcnt \times dep[x_2][1].mxcnt = D\_cnt$$

我们考虑一条边$x_1 \leftrightarrow x_2$，其中$x_1$处在非必经边上——比如共用路径$L$的左侧，$x_2$处在必经边上，那么必有$dep[x_1][0] < dep[x_2][0]$，这是因为有部分直径已从$x_2$处分岔，不再为从$x_1$向左出发的最长链提供方案，否则这条边仍然是必经边。参见下图。

所以，现在我们只需要：

1. 通过两遍DFS找出任意一条直径及其具体路径；
2. 以直径两端点为根，求出所有节点的$dep[x][0,1]$；
3. 依次扫描求出的这条直径上的所有边，检查其两点是否符合上述判定条件；

记变量$cur$为已处理的扫描结果中合法的$dep[x_1][0].mxcnt \times dep[x_1][1].mxcnt$的最大值。显然，$cur$的最大值就是$D\_cnt$，所以之前我认为，我们没有必要先去找出$D\_cnt$的具体值是多少。当某条边的$$dep[x_1][0].mxcnt \times dep[x_1][1].mxcnt = dep[x_2][0].mxcnt \times dep[x_2][1].mxcnt$$时，检查$cur$和它的大小关系。若$cur$较其小，则重置答案为$ans = 1$（认为只有当前这条边是必经边），并更新$cur$；若$cur$和它相等，则答案累加$1$——这是一条新的必经边。

但现在我们回过头来，看它能不能应对菊花图。假设我们有一张菊花图$G$，共$n$个点，$1$号点连接了$n-1$条边。则可以推出$dep[1][0].mxcnt=dep[1][1].mxcnt=n-1$。虽然会计算出错误的总直径条数，但答案仍然$ans$变量的初始值$0$——因为没有任何一条边满足能够更新$cur$的条件；但在“每个分支长度均为$2$的菊花图”上，这样做会出问题——直径的第一条和最后一条边将满足以上条件（参见下图）。所以，我们仍然需要先找出$D\_cnt$，再对每条边作判断。

每个分支长度均为2的菊花图

最终我们进行了$4$次$\mathrm{O}(N)$的DFS和$2$次$\mathrm{O}(N)$的节点扫描，最终时间复杂度为大常数的$\mathrm{O}(N)$，非常优秀。

边权$w \in [1, 10^9] \cap \mathbb{N}$。记得开long long。

R58557274 记录详情 （已修正）

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
#include <bits/stdc++.h>
using namespace std;

const int N = 204800;
int n, x, y, z, e_cnt, head[N];
int p[2], from[N], path[N], p_cnt, ans;
long long d[N], D, td, cur;
struct data {
	long long mx, mxcnt;
} dep[N][2];
struct edge {
	int v, w, nxt;
} e[N<<1];
void add_e (int x, int y, int z) {
	e[++e_cnt].nxt = head[x], head[x] = e_cnt,
	e[e_cnt].v = y, e[e_cnt].w = z;
}

void dfs (int x, int fa, bool rec = 0) {
	if (td < d[x]) td = d[x], p[rec] = x;
	for (int i = head[x]; i; i = e[i].nxt) {
		if (e[i].v == fa) continue;
		d[e[i].v] = d[x] + e[i].w;
		from[e[i].v] = x;
		dfs (e[i].v, x, rec);
	}
}

void dp (int x, int fa, bool rec) {
	dep[x][rec].mxcnt = 1;
	for (int i = head[x]; i; i = e[i].nxt) {
		if (e[i].v == fa) continue;
		dp (e[i].v, x, rec);
		if (dep[e[i].v][rec].mx + e[i].w > dep[x][rec].mx)
			dep[x][rec].mx = dep[e[i].v][rec].mx + e[i].w,
			dep[x][rec].mxcnt = dep[e[i].v][rec].mxcnt;
		else if (dep[e[i].v][rec].mx + e[i].w == dep[x][rec].mx)
			dep[x][rec].mxcnt += dep[e[i].v][rec].mxcnt;
	}
}

int main () {
	/* 洛谷题库 P3304 [SDOI2013]直径 吴秋实 */
	scanf ("%d", &n);
	for (int i = 1; i < n; ++i) {
		scanf ("%d%d%d", &x, &y, &z);
		add_e (x, y, z);
		add_e (y, x, z);
	}
	// 求出一条直径 
	dfs (1, 0);
	from[p[0]] = td = d[p[0]] = 0;
	dfs (p[0], 0, 1);
	D = td; x = p[1];
	while (x)
		path[++p_cnt] = x,
		x = from[x];
	// 将直径两端点分别作根，求每个点的最大深度及其计数 
	dp (p[0], 0, 0);
	dp (p[1], 0, 1);
	// 计算直径条数 
	for (int i = 1; i <= p_cnt; ++i)
		cur = max (cur, dep[path[i]][0].mxcnt * dep[path[i]][1].mxcnt);
	// 扫描并依次判定 
	for (int i = 2; i <= p_cnt; ++i)
		ans +=
		  (dep[path[i]][0].mxcnt * dep[path[i]][1].mxcnt == dep[path[i - 1]][0].mxcnt * dep[path[i - 1]][1].mxcnt)
		  && (dep[path[i]][0].mxcnt * dep[path[i]][1].mxcnt == cur);
	
	printf ("%lld\n%d", D, ans);
	
	return 0;
}

（所以换根DP到底能不能做？）