題目大意：給出一棵帶權(quán)樹，規(guī)定 ，解釋一下就是當確定三個點 u1 , u2 , u3 后，需要找到一個點 v 到三個點的距離之和最小，現(xiàn)在給出 u1 , u2 , u3 的可行取值，問 f 函數(shù)的期望是多少

題目分析：考慮轉(zhuǎn)換模型，對于給定的 u1 , u2 和 u3 來說，不難猜出點 v 是唯一存在的（不會證明），相應(yīng)的這個最短的距離之和也是唯一確定的，且可以表示為?

這樣一來根據(jù)兩個期望的基本公式進行轉(zhuǎn)換：

E( X + Y ) = E( X ) + E( Y )

E( CX ) = CE( X )

如此一來就將 u1 , u2 , u3 的貢獻拆成了分別獨立的三組，再考慮對于 E( dis( u , v ) ) 該如何去求

現(xiàn)在問題就是如何快速求出 E( dis( u1 , u2 ) ) 了

接下來一個思維點就是，需要想到計算每條邊的貢獻，具體就是，對于一條邊 ( u , v ) 來說，當移除掉這條邊后，整棵樹將會被分成不連通的兩個部分，記為 T1 和 T2，比較顯然的是：

T1 中的 u1 到 T2 中的 u2 必然會經(jīng)過當前邊

T1 中的 u2 到 T2 中的 u1 必然會經(jīng)過當前邊

直接樹形 dp 就好了

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;vector<pair<int,int>>node[N];LL sz[4][N],cnt[4];double ans=0;void dfs1(int u,int fa) {for(auto it:node[u]){int v=it.first;if(v==fa)continue;dfs1(v,u);for(int i=1;i<=3;i++)sz[i][u]+=sz[i][v];} }void dfs2(int u,int fa) {for(auto it:node[u]){int v=it.first,w=it.second;if(v==fa)continue;dfs2(v,u);for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)if(i!=j)ans+=1.0*(sz[i][1]-sz[i][v])*sz[j][v]*w/cnt[i]/cnt[j]/2;} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);node[u].emplace_back(v,w);node[v].emplace_back(u,w);}for(int i=1;i<=3;i++){scanf("%d",cnt+i);for(int j=1;j<=cnt[i];j++){int x;scanf("%d",&x);sz[i][x]++;}}dfs1(1,-1);dfs2(1,-1);printf("%.10f\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的2020CCPC(威海) - Rencontre(树形dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。