[BZOJ1509][NOI2003]逃學的小孩

1509: [NOI2003]逃學的小孩

Time Limit: 5 Sec??Memory Limit: 64 MB
Submit: 968??Solved: 489
[Submit][Status][Discuss]

Description

Input

第一行是兩個整數N（3 ? N ? 200000）和M，分別表示居住點總數和街道總數。以下M行，每行給出一條街道的信息。第i+1行包含整數Ui、Vi、Ti（1?Ui, Vi ? N，1 ? Ti ? 1000000000），表示街道i連接居住點Ui和Vi，并且經過街道i需花費Ti分鐘。街道信息不會重復給出。

Output

僅包含整數T，即最壞情況下Chris的父母需要花費T分鐘才能找到Chris。

Sample Input

4 3
1 2 1
2 3 1
3 4 1

Sample Output

4

枚舉每個點為三條路徑的交點，設到這個點的第一、二、三長鏈的長度分別為$x,y,z$，則最長路徑為$x+2*y+z$

注意可能從父親那里有一條鏈連過來，所以dfs兩遍

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char buf[10000000], *ptr = buf - 1;
inline int readint() {int n = 0;char ch = *++ptr;while (ch< '0' || ch > '9') ch = *++ptr;while (ch <= '9' && ch >= '0') {n = (n << 1) + (n << 3) + ch - '0';ch = *++ptr;}return n;
}
typedef long long ll;
const int maxn = 200000 + 10;
const ll INF = 1LL << 60;
struct Edge {int to, val, next;Edge() {}Edge(int _t, int _v, int _n) : to(_t), val(_v), next(_n) {}
}e[maxn * 2];
int fir[maxn] = { 0 }, cnt = 0;
inline void ins(int u, int v, int w) {e[++cnt] = Edge(v, w, fir[u]); fir[u] = cnt;e[++cnt] = Edge(u, w, fir[v]); fir[v] = cnt;
}
int fa[maxn];
ll mx1[maxn], mx2[maxn], mx3[maxn], f[maxn];
void dfs1(int u) {mx1[u] = mx2[u] = mx3[u] = 0;for (int v, i = fir[u]; i; i = e[i].next) {v = e[i].to;if (v == fa[u]) continue;fa[v] = u;dfs1(v);mx3[u] = max(mx3[u], mx1[v] + e[i].val);if (mx3[u] > mx2[u]) swap(mx3[u], mx2[u]);if (mx2[u] > mx1[u]) swap(mx2[u], mx1[u]);}
}
void dfs2(int u) {for (int v, i = fir[u]; i; i = e[i].next) {v = e[i].to;if (v == fa[u]) continue;f[v] = f[u] + e[i].val;if (mx1[v] + e[i].val == mx1[u])f[v] = max(f[v], mx2[u] + e[i].val);elsef[v] = max(f[v], mx1[u] + e[i].val);dfs2(v);}
}
ll ans = 0;
inline void solve(ll &x, ll &y, ll &z) {if (z > y) swap(z, y);if (y > x) swap(y, x);ans = max(ans, x + (y << 1) + z);
}
int main() {fread(buf, sizeof(char), sizeof(buf), stdin);int n = readint();readint();for (int u, v, w, i = 1; i < n; i++) {u = readint();v = readint();w = readint();ins(u, v, w);}fa[1] = 0;dfs1(1);f[1] = 0;dfs2(1);for (int i = 1; i <= n; i++)if (f[i] < mx3[i]) solve(mx1[i], mx2[i], mx3[i]);else solve(mx1[i], mx2[i], f[i]);printf("%lld\n", ans);return 0;
}

?