2010年02月28日星期日.sgu149
sgu149:tree dp
這個(gè)題想了好久，第一遍代碼寫的太亂了，然后就重新寫了一遍，還好過了。。
思路就是每個(gè)點(diǎn)的最長距離有兩個(gè)來源，一個(gè)是子節(jié)點(diǎn)，一個(gè)是父節(jié)點(diǎn)。
字節(jié)點(diǎn)的即是深度，這個(gè)好求。
如果是來自父節(jié)點(diǎn)，那么假定父節(jié)點(diǎn)的最長距離已經(jīng)獲得，
如果這個(gè)最長距離不是來自當(dāng)前節(jié)點(diǎn)，就可一直接加上父節(jié)點(diǎn)到這個(gè)節(jié)點(diǎn)的邊長。
如果這個(gè)最長距離恰好來自這個(gè)節(jié)點(diǎn)，那么可以使用父節(jié)點(diǎn)不來自這個(gè)節(jié)點(diǎn)的最長路來做同樣的事情。
?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://m.shnenglu.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?