一道树的直径
树网的核 BZOJ原题链接
树网的核 洛谷原题链接
消防 BZOJ原题链接
消防 洛谷原题链接
一份代码四倍经验，爽
显然要先随便找一条直径，然后直接枚举核的两个端点，对每一次枚举的核遍历核上的每个点，用\(dfs\)求出核外节点到核的最大值即可，时间复杂度为\(O(n^3)\)，这在\(NOIP\)的原数据范围下是可以过的，但对于数据加强版就必须要优化了。
发现当枚举到直径上的某个点时，核的另一端在不超过\(s\)的前提下显然越远越好。这样就直接优化掉一个\(n\)了，但我们还可以继续优化。
设直径上的点为\(u_1,u_2,\dots,u_t\)，当前枚举到的核的两端点为\(x_i,x_j\)。
根据直径的最长性，我们可以发现对于该核的偏心距实际上就是\(\max\{\max\limits_{k=1}^{t}\{d[u_k]\},dis(u_1,x_i),dis(x_j,u_t)\}\)，数组\(d\)表示直径外节点（不经过直径上的点）到\(u_k\)的最大值，\(dis\)表示两点间的距离。
而\(\max\limits_{k=1}^{t}\{d[u_k]\}\)显然是个定值，至于\(dis\)，我们可专门剖出直径上的所有边，然后用在枚举核的左端点时用两个变量维护即可，时间复杂度\(O(n)\)。
#include<cstdio>
using namespace std;
const int N = 5e5 + 10;
struct dd {
int dis, x;
};
dd D[N], a[N];
int fi[N], di[N << 1], da[N << 1], ne[N << 1], l, ma;
bool v[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c<'0' || c>'9'; c = getchar())
p |= c == '-';
for (; c >= '0'&&c <= '9'; c = getchar())
x = x * 10 + (c - '0');
return p ? -x : x;
}
inline int maxn(int x, int y)
{
return x > y ? x : y;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
inline void add(int x, int y, int z)
{
di[++l] = y;
da[l] = z;
ne[l] = fi[x];
fi[x] = l;
}
void dfs(int x, int fa, int dis, int la)
{
int i, y;
if (dis > ma)
{
ma = dis;
D[0].x = x;
}
D[x].x = fa;
D[x].dis = la;
for (i = fi[x]; i; i = ne[i])
{
y = di[i];
if (y != fa)
dfs(y, x, dis + da[i], da[i]);
}
}
void dfs_2(int x, int dis)
{
int i, y;
v[x] = 1;
if (dis > ma)
ma = dis;
for (i = fi[x]; i; i = ne[i])
{
y = di[i];
if (!v[y])
dfs_2(y, dis + da[i]);
}
}
int main()
{
int i, j, n, m, x, y, z, s = 0, k = 0, tail = 0, head = 0, an = 1e9;
n = re();
m = re();
for (i = 1; i < n; i++)
{
x = re();
y = re();
z = re();
add(x, y, z);
add(y, x, z);
}
dfs(1, 0, 0, 0);
ma = 0;
dfs(D[0].x, 0, 0, 0);
for (i = D[0].x; i; i = D[i].x)
{
v[i] = 1;
a[++k].x = i;
a[k].dis = D[i].dis;
}
ma = 0;
for (i = 1; i <= k; i++)
dfs_2(a[i].x, 0);
for (j = 1; j < n; j++)
if (s + a[j].dis <= m)
s += a[j].dis;
else
break;
for (i = j; i < n; i++)
tail += a[i].dis;
an = minn(an, maxn(ma, maxn(head, tail)));
for (i = 1; i < n; i++)
{
s -= a[i].dis;
head += a[i].dis;
for (; j < n; j++)
if (s + a[j].dis <= m)
{
s += a[j].dis;
tail -= a[j].dis;
}
else
break;
an = minn(an, maxn(ma, maxn(head, tail)));
}
printf("%d", an);
return 0;
}