?

題面

?

? ? 顯然的一個建模是，每個葉子對應一個權值，代表比最晚的葉子早了多久，然后我們要做的就是給每條邊賦上值，使得每個葉子到根的路徑上的所有邊權值和等于葉子的權值。

? ? 我們貪心的想一想，必然是離根越近的邊賦值多的情況比較優(在保證同步的情況下)，因為離根越近的邊影響的葉子會更多。

? ? 而對于兩個節點 u,v，我們必須要在lca(u,v)以下的邊中賦值使得 u和v同步，因為再往上的邊對u和v的影響就相同了。

? ? 于是根據以上兩點，可以得到一個比較簡單的dp。

? ? ?f[x]表示以x為根的子樹所有葉子同步的最小代價，轉移很簡單，留給大家想了w

?

#include<bits/stdc++.h> #define ll long long using namespace std; const int N=500005;int hd[N],ne[N*2],to[N*2],val[N*2],num,n,S,mx[N]; ll f[N];inline void add(int x,int y,int z){to[++num]=y,ne[num]=hd[x],hd[x]=num,val[num]=z; } inline int read(){int x=0; char ch=getchar();for(;!isdigit(ch);ch=getchar());for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';return x; }void dfs(int x,int fa){for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa)dfs(to[i],x),mx[x]=max(mx[x],mx[to[i]]+val[i]);for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa)f[x]+=f[to[i]]+mx[x]-mx[to[i]]-val[i]; }int main(){n=read(),S=read();for(int i=1,u,v,w;i<n;i++) u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);dfs(S,0);printf("%lld\n",f[S]);return 0; }

　　

轉載于:https://www.cnblogs.com/JYYHH/p/11258074.html

總結

以上是生活随笔為你收集整理的[ZJOI2007] 时态同步的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。