【题目来源】
【个人体会】这个题目刚开始看的时候我以为是树的中心点+最小割。但是最小割那边我很怕会超时，因此一开始就没敢打，后来发现可以使用树形DP在O(N)的级别中解决这个问题，因此思路很明确，首先是求树的中心点，然后是树形DP，总级别也是O(N)，可能带点常数，但无关紧要。
【题目解析】思路分为两块，第一块是求树的中心点，有经典的O(N)级别的算法。第二块是树形DP，DP[U]表示的是以U为根的子树中，切断所有叶子节点与根节点的联系，所要付出的那个最大边的代价。因此，对于U和U的某个儿子V，在cost[U,V]和DP(V)中选一个小的，记为min{cost[U,V], DP(V)}，最后在所有的min{cost[U,V], DP(V)}中选一个max用来更新DP(U)
【代码如下】
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 12 #define rep(i, x) for (int i = 1; i <= x; ++i) 13 #define rept(i, x) for (int i = 0; i < x; ++i) 14 #define pb push_back 15 #define ppf pop_front 16 #define mp make_pair 17 #define pf push_front 18 #define x first 19 #define y second 20 21 #define FILE_IO 22 #define DEBUG 23 24 using namespace std; 25 26 typedef long long int64; 27 28 const int Max = 10001, MAX = 1e16 + 1; 29 30 struct edge 31 { 32 int v, c, next; 33 int64 w; 34 }E[Max * 2]; 35 36 bool hash[Max]; 37 int N, Cnt, H[Max], Root; 38 int64 Dp[Max], up[Max], down[Max][3]; 39 40 void Clear() 41 { 42 Cnt = 0; 43 memset(H, 0, sizeof(H)); 44 memset(up, 0, sizeof(up)); 45 memset(down, 0, sizeof(down)); 46 } 47 48 int64 Treedp_Dp(int i) 49 { 50 if (Dp[i] != -1) return Dp[i]; 51 int64 t1 = MAX, t2 = 0; 52 bool flag = false; 53 for (int j = H[i], v; j; j = E[j].next) 54 { 55 v = E[j].v; 56 if (!hash[v]) hash[v] = flag = true; 57 else continue; 58 t1 = min(Treedp_Dp(v), E[j].w), t2 = max(t2, t1); 59 } 60 if (!flag) return MAX; 61 Dp[i] = t2; 62 return t2; 63 } 64 65 void Treedp() 66 { 67 memset(Dp, -1, sizeof(Dp)); 68 memset(hash, 0, sizeof(hash)); hash[Root] = true; 69 printf("%lld\n", Treedp_Dp(Root)); 70 } 71 72 void Center_find() 73 { 74 int64 t1 = 0, t2 = MAX; 75 for (int i = 1; i <= N; ++i) 76 { 77 t1 = max(up[i], down[i][1]); 78 if (t1 < t2) t2 = t1, Root = i; 79 } 80 } 81 82 void Center_upFind(int u, int fa, int64 dis) 83 { 84 if (u != fa) 85 { 86 up[u] = up[fa] + dis; 87 int64 tmp = 0; 88 if (down[fa][1] == down[u][1] + dis) tmp = down[fa][2] + dis; 89 else tmp = down[fa][1] + dis; 90 if (tmp > up[u]) up[u] = tmp; 91 } 92 for (int j = H[u], v; j; j = E[j].next) 93 { 94 v = E[j].v; 95 if (hash[v]) continue; 96 hash[v] = true; 97 Center_upFind(v, u, E[j].c); 98 } 99 }100 101 void Center_downFind(int u)102 {103 for (int j = H[u], v; j; j = E[j].next)104 {105 v = E[j].v;106 if (hash[v]) continue;107 hash[v] = true;108 Center_downFind(v);109 if (down[v][1] + E[j].c > down[u][1])110 {111 down[u][2] = down[u][1];112 down[u][1] = down[v][1] + E[j].c;113 }114 else if (down[v][1] + E[j].c > down[u][2]) down[u][2] = down[v][1] + E[j].c;115 }116 }117 118 void Center()119 {120 memset(hash, 0, sizeof(hash)); hash[1] = true;121 Center_downFind(1);122 memset(hash, 0, sizeof(hash)); hash[1] = true;123 Center_upFind(1, 1, 0);124 Center_find();125 }126 127 inline void edgeAdd(int &x, int &y, int &c, int &w)128 {129 E[++ Cnt].next = H[x], H[x] = Cnt, E[Cnt].v = y, E[Cnt].c = c, E[Cnt].w = w;130 }131 132 void Init()133 {134 for (int i = 1, x, y, c, w; i <= N - 1; ++i)135 {136 scanf("%d%d%d%d", &x, &y, &c, &w);137 edgeAdd(x, y, c, w);138 edgeAdd(y, x, c, w);139 }140 }141 142 int main()143 {144 #ifdef FILE_IO145 //freopen("test.in", "r", stdin);146 #endif // FILE_IO147 while (scanf("%d", &N) != EOF)148 {149 Init();150 Center();151 Treedp();152 Clear();153 }154 return 0;155 }