【ZOJ月赛】【树形DP】【I.Destroy】

【题目来源】http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=4937

【个人体会】这个题目刚开始看的时候我以为是树的中心点+最小割。但是最小割那边我很怕会超时，因此一开始就没敢打，后来发现可以使用树形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 #include <iostream>
  2 #include <cstdio>
  3 #include <climits>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <vector>
  7 #include <deque>
  8 #include <stack>
  9 #include <queue>
 10 #include <algorithm>
 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_IO
145     //freopen("test.in", "r", stdin);
146     #endif // FILE_IO
147     while (scanf("%d", &N) != EOF)
148     {
149         Init();
150         Center();
151         Treedp();
152         Clear();
153     }
154     return 0;
155 }