P1099 树网的核 - 树的直径 + 单调队列

题目

题目描述

设 $T=(V,E,W)$ 是一个无圈且连通的无向图（也称为无根树），每条边到有正整数的权，我们称 $T$ 为树网（treenetwork），其中 $V$，$E$ 分别表示结点与边的集合，$W$ 表示各边长度的集合，并设 $T$ 有 $n$ 个结点。

路径：树网中任何两结点 $a$，$b$ 都存在唯一的一条简单路径，用 $d(a, b)$ 表示以 $a, b$ 为端点的路径的长度，它是该路径上各边长度之和。我们称 $d(a, b)$ 为 $a, b$ 两结点间的距离。

$D(v, P)=\min\{d(v, u)\}$, $u$ 为路径 $P$ 上的结点。

树网的直径：树网中最长的路径成为树网的直径。对于给定的树网 $T$，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

偏心距 $\mathrm{ECC}(F)$：树网 $T$ 中距路径 $F$ 最远的结点到路径 $F$ 的距离，即

$\mathrm{ECC}(F)=\max\{d(v, F),v \in V\}$

任务：对于给定的树网 $T=(V, E, W)$ 和非负整数 $s$，求一个路径 $F$，他是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过 $s$（可以等于 $s$），使偏心距 $ECC(F)$ 最小。我们称这个路径为树网 $T=(V, E, W)$ 的核（Core）。必要时，$F$ 可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

下面的图给出了树网的一个实例。图中，$A-B$ 与 $A-C$ 是两条直径，长度均为 $20$。点 $W$ 是树网的中心，$EF$ 边的长度为 $5$。如果指定 $s=11$，则树网的核为路径DEFG（也可以取为路径DEF），偏心距为 $8$。如果指定 $s=0$（或 $s=1$、$s=2$），则树网的核为结点 $F$，偏心距为 $12$。

输入格式

共 $n$ 行。

第 $1$ 行，两个正整数 $n$ 和 $s$，中间用一个空格隔开。其中 $n$ 为树网结点的个数，$s$ 为树网的核的长度的上界。设结点编号以此为 $1,2\dots,n$。

从第 $2$ 行到第 $n$ 行，每行给出 $3$ 个用空格隔开的正整数 $u, v, w$，依次表示每一条边的两个端点编号和长度。例如，2 4 7 表示连接结点 $2$ 与 $4$ 的边的长度为 $7$。

输出格式

一个非负整数，为指定意义下的最小偏心距。

输入输出样例

输入 #1 复制

5 2
1 2 5
2 3 2
2 4 4
2 5 3

输出 #1 复制

5

输入 #2 复制

8 6
1 3 2
2 3 2 
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3

输出 #2 复制

5

说明/提示

• 对于 $40\%$ 的数据，保证 $n \le 15$。
• 对于 $70\%$ 的数据，保证 $n \le 80$。
• 对于 $100\%$ 的数据，保证 $n \le 300$，$0\le s\le10^3$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^3$。

题解

因为路径$F$是直径上的一部分，那就变得非常好办了。考虑下图的样子：

求出在这种情况之下的子树的最深深度，记为$sd\text{ }secd[i]$，其中$i$为直径上的点，之所以这么表示，因为这个深度是在一个节点所有子树当中第二深的深度，最深的深度$sd\text{ }max[i]$为直径所在的那颗子树的深度。

在这种情况下，可以在直径上选定一段$F$后，列出$ECC(F)$的方程：

$$ECC(F) = \max \begin {cases} \text{left of}~F~\text{in diameter}\\ \max \{sd\_secd[i],~i\in F\} \\ \text{right of}~F~\text{in diameter} \end {cases}$$

因为求上面是式子中的第一项和第三项非常容易，在直径求完之后就是$O(1)$了，而第二项是区间最大值，那么我们可以用单调队列维护。

题解

#include <iostream>
#include <cstring>
#define int long long 

using namespace std;

const int maxn = 305;
int h[maxn], ecnt = 2, n, s;
struct edge { int to, next, w; } g[maxn << 1];
void add_edge(int u, int v, int w) { g[ecnt] = (edge) { v, h[u], w }; h[u] = ecnt ++; }
struct node { int pos, val; } q[maxn];

// sd_max: maximum depth of subtree
// sd_secd: second maximum depth of subtree
int dis[maxn], sd_max[maxn], sd_secd[maxn], next[maxn], dia[maxn], head, tail; 
	
int dfs1(int u, int fa) {
	int alpha = u;
	for (int e = h[u]; e; e = g[e].next) {
		int v = g[e].to;
		if (v == fa) continue;
		dis[v] = dis[u] + g[e].w;
		int a = dfs1(v, u);
		if (dis[a] >= dis[alpha]) alpha = a;
	}
	return alpha;
}

void dfs2(int u, int fa) {
	for (int e = h[u]; e; e = g[e].next) {
		int v = g[e].to;
		if (v == fa) continue;
		dis[v] = dis[u] + g[e].w;
		dfs2(v, u);
		int this_depth = sd_max[v] + g[e].w;
		if (this_depth >= sd_max[u]) {
			sd_secd[u] = sd_max[u];
			sd_max[u] = this_depth;
			next[u] = v;
		} else if (this_depth > sd_secd[u]) {
			sd_secd[u] = this_depth;
		}
	}
}

void inc(long long &i) {
	i ++;
	while (head < tail && q[head].pos == i - 1) head ++;
}

signed main() {
	cin >> n >> s;
	for (int i = 1; i < n; i ++) {
		int u, v, w; cin >> u >> v >> w;
		add_edge(u, v, w);
		add_edge(v, u, w);
	}
	int ds = dfs1(1, 0);
	dis[ds] = 0;
	dfs2(ds, 0);
	int k = 0;
	for (int p = ds; p; p = next[p])
		dia[++ k] = p;
		
		
//	for (int i = 1; i <= k; i ++) cout << dia[i] << endl;
//	for (int i = 1; i <= k; i ++) cout << sd_secd[dia[i]] << endl; 
//	for (int i = 1; i <= k; i ++) cout << dis[dia[i]] << endl; 
	
	
	int ans = 8e18;
	head = 0, tail = 0;
	for (int i = 1, j = 1; i <= k; inc(i)) {
		int u = dia[i];
		while (j + 1 <= k + 1 && dis[dia[j]] - dis[u] <= s) {
			while (head < tail && q[tail - 1].val <= sd_secd[dia[j]]) tail --;
			q[tail ++] = (node) { j, sd_secd[dia[j]] };
			j ++;
		}
		int tmp = max(dis[u], dis[dia[k]] - dis[dia[j - 1]]);
		tmp = max(tmp, q[head].val);
		ans = min(ans, tmp);
	}
	cout << ans << endl;
	return 0;
}