1509: [NOI2003]逃学的小孩
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 968 Solved: 489[][][]Description
Input
第一行是两个整数N（3 N 200000）和M，分别表示居住点总数和街道总数。以下M行，每行给出一条街道的信息。第i+1行包含整数Ui、Vi、Ti（1Ui, 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#include #include 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); else f[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;}