正題

---

題目大意

一棵樹，可以增長邊權長度，要求根節點要每個葉子節點路徑長度相等，求最少增加次數。

---

解題思路

肯定優先修改上面的邊，因為這樣可以影響最多的點，那么對于每個節點我們都要使它到每個它子樹中葉子節點的長度相等就好了。直接樹形$dp$。

---

$code$

#include<cstdio> #include<algorithm> #define ll long long using namespace std; const ll N=500010; struct node{ll to,w,next; }a[N*2]; ll ls[N],tot,last[N],f[N],s,n; void addl(ll x,ll y,ll w) {a[++tot].to=y;a[tot].w=w;a[tot].next=ls[x];ls[x]=tot; } void dp(ll x,ll fa,ll w) {last[x]=w;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa) continue;dp(y,x,w+a[i].w);last[x]=max(last[y],last[x]);}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa) continue;f[x]+=f[y];if(last[y]<last[x])f[x]+=last[x]-last[y];} } int main() {scanf("%lld%lld",&n,&s);for(ll i=1;i<n;i++){ll x,y,w;scanf("%lld%lld%lld",&x,&y,&w);addl(x,y,w);addl(y,x,w);}dp(s,0,0);printf("%lld",f[s]); }

總結

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

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