【HDU2196 Computer】经典树形dp

http://acm.hdu.edu.cn/showproblem.php?pid=2196

题意：有n台电脑相连，让你求每台电脑与离它最远的那台电脑的距离。

思路：两遍搜索即可，第一遍从上到下，第二遍从小往上。对于某点，该点的最长半径为此点离自己孩子的最大距离和父亲节点传递下来的最长距离加连接此点的权值，两者之间选择最大值，但这里处理的时候要注意了，某点的孩子距离和父亲传递下来的最大距离可能为同一路径，因为父亲节点的最大距离可能经过此点。所以在处理的过程中不仅要随时记录最长路径，还要记录一个次长路径。这里WA了几次，更新最长路径的时候，记得要提前把最长路径传递给次长路径。

讲的很绕口。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <map>

 #include <vector>

 #include <algorithm>

 using namespace std;

 typedef long long lld;

 const lld maxn=;

 lld fmax[maxn], smax[maxn];

 int pre[maxn];

 map<int,map<int,int> >mp;

 struct Node

 {

     int v, val;

     Node(){}

     Node(int v_, int val_)

     {

         v=v_, val=val_;

     }

 };

 vector<Node>vt[maxn];

 void dfs(int u)

 {

     for(int i=; i<vt[u].size(); i++)

     {

         int v=vt[u][i].v, val=vt[u][i].val;

         dfs(v);

         if(fmax[v]+val>fmax[u]) smax[u]=fmax[u],fmax[u]=fmax[v]+val; ///这里要注意了，更新fmax的同时要把fmax传递给smax（最大传递给次大）

         else if(fmax[v]+val>smax[u]) smax[u]=fmax[v]+val;

     }

 }

 void DFS(int u)

 {

     if(u==) ;

     else

     {

         int fa=pre[u], val=mp[fa][u];

         if(fmax[u]==fmax[fa]-val)

         {

             if(smax[fa]+val>fmax[u]) smax[u]=fmax[u], fmax[u]=smax[fa]+val;

             else if(smax[fa]+val>smax[u]) smax[u]=smax[fa]+val;

         }

         else

         {

             if(fmax[fa]+val>fmax[u]) smax[u]=fmax[u], fmax[u]=fmax[fa]+val;

             else if(fmax[fa]+val>smax[u]) smax[u]=fmax[fa]+val;

         }

     }

     for(int i=; i<vt[u].size(); i++)

         DFS(vt[u][i].v);

 }

 int main()

 {

     int n;

     while(cin >> n)

     {

         mp.clear();

         for(int i=; i<=n; i++) fmax[i]=smax[i]=, pre[i]=, vt[i].clear();

         for(int i=; i<=n; i++)

         {

             int u, val;

             scanf("%d%d",&u,&val);

             vt[u].push_back(Node(i,val));

             mp[u][i]=val;

             pre[i]=u;

         }

         dfs();

         DFS();

         for(int i=; i<=n; i++)

             cout << fmax[i] <<endl;

     }

     return ;

 }

 /*

 8

 1 1

 1 2

 2 2

 2 4

 3 3

 3 4

 4 3

 */

巴特西

【HDU2196 Computer】经典树形dp

最新文章

热门文章