hdu 2196(树上点分治）

题意：

　　n个节点无根树，求从每个节点出发的最长链

解决：

　　最长链有两种可能：1、以自身为根的子树上，从根到叶子节点的某条链。 2、从自己出发，向上到父节点，加上父节点的最长链。

　　但是第二种情况有很多问题，首先，如果父节点的最长链是通过要求节点的话，我们就要用到父节点的次长链。并且还要判断，我们需要用的这条最长链，或者次长链，跟父节点向上到父节点的最长链的比较。

　　所以先dfs一遍处理出每个点以自身为根的子树上的最长链，次长链，以及最长链对应经过哪一个子节点。

　　再dfs一次维护出每个结点向上到父节点所能走出的最长链。

　　最终答案就是max (子树上最长链，向上到父节点的最长链）

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 
  5 const int MAXN = 100010;
  6 
  7 struct DPNode{
  8     long long first, second, fa;
  9     int v1;
 10 }dp[10010];
 11 
 12 struct Edge{
 13     int u, v, next;
 14        long long cost;
 15     Edge(){}
 16     Edge(int u, int v, long long cost, int next)
 17     {
 18         this->u = u;
 19         this->v = v;
 20         this->cost = cost;
 21         this->next = next;
 22     }
 23 }edge[MAXN<<1];
 24 int head[MAXN];
 25 int tot;
 26 int n;
 27 bool vis[MAXN];
 28 
 29 void addEdge(int u, int v, long long cost)
 30 {
 31     edge[++tot] = Edge(u, v, cost, head[u]);
 32     head[u] = tot;
 33 }
 34 
 35 void init()
 36 {
 37     tot = 1;
 38     memset(head, 0, sizeof head);
 39 }
 40 
 41 void dfs1(int u)
 42 {
 43     vis[u] = true;
 44     dp[u].first = dp[u].second = dp[u].v1 = 0 ;
 45     for (int i = head[u]; i > 0; i = edge[i].next) {
 46         int v = edge[i].v;
 47         long long cost = edge[i].cost;
 48         if (vis[v] == false) {
 49             dfs1(v);
 50             if (dp[v].first + cost > dp[u].first) {
 51                 dp[u].second = dp[u].first;
 52                 dp[u].first = dp[v].first + cost;
 53 
 54                 dp[u].v1 = v;
 55             }
 56             else if (dp[v].first + cost > dp[u].second) {
 57                 dp[u].second = dp[v].first;
 58             }
 59         }
 60     }
 61 }
 62 
 63 void dfs2(int u)
 64 {
 65     vis[u] = true;
 66     for (int i = head[u]; i > 0; i = edge[i].next) {
 67         int v = edge[i].v;
 68         long long cost = edge[i].cost;
 69         if (vis[v] == false) {
 70             //printf("u = %d, v = %d:
", u, v);
 71             if (dp[u].v1 == v) {
 72                 dp[v].fa = cost + std::max(dp[u].fa, dp[u].second);
 73             }
 74             else {
 75                 dp[v].fa = cost + std::max(dp[u].fa, dp[u].first);
 76             }
 77             //printf("fa = %d
", dp[v].fa);
 78             dfs2(v);
 79         }
 80     }
 81 }
 82 
 83 int main()
 84 {
 85     while (~scanf("%d", &n)) {
 86         init();
 87         for (int i = 2; i <= n; ++ i) {
 88             int v;
 89             long long cost;
 90             scanf("%d%lld", &v, &cost);
 91             addEdge(i, v, cost);
 92             addEdge(v, i, cost);
 93         }
 94         memset(vis, false, sizeof vis);
 95         dfs1(1);
 96         memset(vis, false, sizeof vis);
 97 //        dp[1].fa = 0;
 98         dfs2(1);
 99         for (int i = 1; i <= n; ++ i) {
100             //printf("i = %d, first = %lld, second = %lld, v1 = %d fa = %lld
", i, dp[i].first, dp[i].second, dp[i].v1, dp[i].fa);
101             printf("%lld
", std::max(dp[i].fa, dp[i].first));
102         }
103     }
104 }

View Code