問題描述

每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是一個(gè)value ，和這個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)

問題解答

設(shè)有n個(gè)節(jié)點(diǎn)。

樹轉(zhuǎn)無向圖，然后用n次dijkstra、spfa等單源最短路算法或1次floyd多源最短路算法求任意兩節(jié)點(diǎn)的值。但是當(dāng)n比較大的話儲(chǔ)存值對(duì)內(nèi)存的開銷較大。

使樹成為有根樹，每個(gè)節(jié)點(diǎn)i儲(chǔ)存到根的距離di。查詢兩節(jié)點(diǎn)di,dj時(shí)，求兩節(jié)點(diǎn)的公共祖先dk，則d(i,j)=di+dj-dk*2。關(guān)于公共祖先可以參考tarjan算法。

當(dāng)成無向圖考慮Floyd算法.