Why so serious? --[NKU]schindlerlee

2010年02月28日星期日.sgu149 tree dp

2010年02月28日星期日.sgu149
sgu149:tree dp
这个题想了好久,第一遍代码写的太乱了,然后就重新写了一遍,还好过了。。

思路就是每个点的最长距离有两个来源,一个是子节点,一个是父节点。
字节点的即是深度,这个好求。
如果是来自父节点,那么假定父节点的最长距离已经获得,
如果这个最长距离不是来自当前节点,就可一直接加上父节点到这个节点的边长。
如果这个最长距离恰好来自这个节点,那么可以使用父节点不来自这个节点的最长路来做同样的事情。

 1 
 2 #define pb(x) push_back(x)
 3 const int N = 10100;
 4 vector<int> g[N];
 5 int deep[N],n,far1[N],far2[N],branch[N],vis[N];
 6 int out[N];
 7 
 8 void dfs1(int u)
 9 {
10   vis[u] = true;
11   int res = 0,idx = 0;
12   for (int i = 0;i < g[u].size();i +=2 ) {
13       int v = g[u][i];
14       int w = g[u][i+1];
15       if (!vis[v]) {
16           dfs1(v);
17           if (res < deep[v] + w) {
18               res = deep[v] + w;
19               idx = v;
20           }
21       }
22   }
23   deep[u] = res;
24 }
25 
26 void dfs2(int u,int cost) // u is current // cost from parent
27 {
28   vis[u] = true;
29   branch[u] = 0;
30   far1[u] = cost;
31   far2[u] = 0;
32 
33   int i,sz = g[u].size();
34   for (i = 0;i < sz;i += 2) {
35       int v = g[u][i];
36       int w = g[u][i+1];
37       if (vis[v]) { continue; } //!
38       if (far1[u] < deep[v] + w ) {
39           far2[u] = far1[u];
40           far1[u] = deep[v] + w ;
41           branch[u] = v;
42       }else if (far2[u] < deep[v] + w ) {
43           far2[u] = deep[v] + w;
44       }
45   }
46   //http://www.cppblog.com/schindlerlee
47   for (i = 0;i < sz;i += 2) {
48       int v = g[u][i];
49       int w = g[u][i+1];
50       if (vis[v]) { continue; }
51       if (v != branch[u]) {
52           dfs2(v,far1[u] + w);
53       }else {
54           dfs2(v,far2[u] + w);
55       }
56   }
57 }
58 
59 int main()
60 {
61   int i,j,k,a,b;
62   scanf("%d",&n);
63   for (i = 2;i <= n;i++) {
64       scanf("%d%d",&a,&b);
65       g[i].pb(a),g[i].pb(b);
66       g[a].pb(i),g[a].pb(b);
67   }
68   dfs1(1);
69   memset(vis,0,sizeof(vis));
70   dfs2(1,0);
71   for ( i = 1; i <= n; i++) {
72       printf("%d\n",far1[i]);
73   }
74 
75   return 0;
76 }
77 

posted on 2010-02-28 21:02 schindlerlee 阅读(1326) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理