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

Problem

【NOIp2007】Core树网的核

Time Limit: $10 Sec$
Memory Limit: $64 MB$

Description

设$T=(V, E, W)$ 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称$T$为树网（$treenetwork$），其中$V, E$分别表示结点与边的集合，$W$表示各边长度的集合，并设$T$有$n$个结点。 路径：树网中任何两结点$a,b$都存在唯一的一条简单路径，用$d(a,b)$表示以$a,b$为端点的路径的长度，它是该路径上各边长度之和。我们称$d(a,b)$为$a,b$两结点间的距离。 一点$v$到一条路径$P$的距离为该点与$P$上的最近的结点的距离： $d(v，P)=min_{u在P上}{d(v，u)}$。 树网的直径：树网中最长的路径称为树网的直径。对于给定的树网$T$，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。 偏心距$ECC(F)$：树网$T$中距路径$F$最远的结点到路径$F$的距离，即 。 任务：对于给定的树网$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$。

Input

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

Output

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

Sample Input

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

Sample Output

5

HINT

对于$70\%$的数据，$n\le 200000$
对于$100\%$的数据，$n\le 500000$, $s<2^{31}$, $所有权值<500$
似乎$SPOJ$上加强版的数据…

标签：树相关

Solution

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

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;}