BZOJ1999【NOIp2007】Core树网的核 <树相关>

Problem

【NOIp2007】Core树网的核

Time Limit:
Memory Limit:

Description

设是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称为树网（），其中分别表示结点与边的集合，表示各边长度的集合，并设有个结点。路径：树网中任何两结点都存在唯一的一条简单路径，用表示以为端点的路径的长度，它是该路径上各边长度之和。我们称为两结点间的距离。一点到一条路径的距离为该点与上的最近的结点的距离：。树网的直径：树网中最长的路径称为树网的直径。对于给定的树网，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。偏心距：树网中距路径最远的结点到路径的距离，即。任务：对于给定的树网和非负整数，求一个路径，它是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过（可以等于），使偏心距最小。我们称这个路径为树网的核（）。必要时，可以退化为某个结点。一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。下面的图给出了树网的一个实例。图中，与是两条直径，长度均为。点是树网的中心，边的长度为。如果指定，则树网的核为路径（也可以取为路径），偏心距为。如果指定（或、），则树网的核为结点，偏心距为。

Input

包含行：第行，两个正整数和，中间用一个空格隔开。其中为树网结点的个数，为树网的核的长度的上界。设结点编号依次为。从第行到第行，每行给出个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“”表示连接结点与的边的长度为。所给的数据都是正确的，不必检验。

Output

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

Sample Input

Sample Output

HINT

对于的数据，
对于的数据，, ,
似乎上加强版的数据…

标签：树相关

Solution

上加强了数据。原题跑再枚举可过。
首先肯定需要两次求直径，求法略。
显然，在长度不超过的前提下，链越长越好（这样偏心距小）。在直径两端到上维护尽可能长的链，找到左右端点到直径做右端点的较大值的最小值。然后由链上各个点出发，找到不经过直径上的点抵达的其他点的最大深度。这个最大深度和之前的最小值中较大的就是答案。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#define MAX_N 500000
#define INF 0x3f3f3f3f
using namespace std;
int n, s, l, r;
vector <int> G[MAX_N+5], E[MAX_N+5];
int d[MAX_N+5], f[MAX_N+5];	bool mrk[MAX_N+5];
void add(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void init() {scanf("%d%d", &n, &s);	for (int i = 1, u, v, c; i < n; i++) scanf("%d%d%d", &u, &v, &c), add(u, v, c), add(v, u, c);}
void DFS(int u) {
    for (int i = 0; i < (int)G[u].size(); i++)	if (G[u][i]^f[u] && !mrk[G[u][i]])
        d[G[u][i]] = d[u]+E[u][i], f[G[u][i]] = u, DFS(G[u][i]);
}
void getD() {
    f[1] = d[1] = 0, DFS(1);	for (int i = 1; i <= n; i++)	if (!r || d[i] > d[r])	r = i;
    f[r] = d[r] = 0, DFS(r);	for (int i = 1; i <= n; i++)	if (!l || d[i] > d[l])	l = i;
    for (int i = l; i; i = f[i])	mrk[i] = true;
}
void sol() {
    int ans = INF;
    for (int i = l, j = l; i; i = f[i]) {
        while (f[j] && d[i]-d[f[j]] <= s)	j = f[j];
        ans = min(ans, max(d[l]-d[i], d[j]));
    }
    for (int i = l; i; i = f[i])	d[i] = 0, DFS(i);
    for (int i = 1; i <= n; i++)	ans = max(ans, d[i]);
    printf("%d", ans);
}
int main() {init(), getD(), sol();	return 0;}