题解 P4408 【[NOI2003]逃学的小孩】
huyufeifei
2018-11-25 11:20:27
大部分思路好像都是先找直径然后再找起点。
我提供另一种思路：找中间点。
可以发现一种合法的路径其实就是在一个点处拉出去三条链(长度可以为0)，其中第二长的链长度翻倍。
然后就用树形DP+二次扫描与换根法做了。
有一个细节就是这三条链不能重复，所以只取每个子树的最长链拿来更新。
代码：
```cpp
#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long LL;
const int N = 200010;
struct Edge {
int nex, v, len;
}edge[N << 1]; int top;
int n, e[N];
LL f[N][3], t[7], ans;
inline void add(int x, int y, int z) {
top++;
edge[top].v = y;
edge[top].len = z;
edge[top].nex = e[x];
e[x] = top;
return;
}
void DFS(int x, int fa) {
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa) {
continue;
}
DFS(y, x);
for(int j = 0; j < 3; j++) {
if(f[x][j] < f[y][0] + edge[i].len) {
for(int k = 2; k > j; k--) {
f[x][k] = f[x][k - 1];
}
f[x][j] = f[y][0] + edge[i].len;
break;
}
}
}
for(int i = 0; i < 3; i++) {
if(f[x][i] < 0) {
f[x][i] = 0;
break;
}
}
return;
}
void DFS_2(int x, int fa, LL dis) {
t[3] = dis;
for(int i = 0; i < 3; i++) {
t[i] = f[x][i];
}
std::sort(t, t + 4);
ans = std::max(ans, t[3] + t[2] + t[2] + t[1]);
LL a = t[3], b = t[2];
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(y == fa) {
continue;
}
if(f[y][0] + edge[i].len == a) {
DFS_2(y, x, b + edge[i].len);
}
else {
DFS_2(y, x, a + edge[i].len);
}
}
return;
}
int main() {
memset(f, ~0x3f, sizeof(f));
int m;
scanf("%d%d", &n, &m);
for(int i = 1, x, y, z; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
DFS(1, 0);
DFS_2(1, 0, 0ll);
printf("%lld", ans);
return 0;
}
```