正題

題目鏈接:http://poj.org/problem?id=3585

---

題目大意

有棵無根樹，當你選擇一個點為根時，價值就是根節(jié)點到所有葉節(jié)點的路上的最小權(quán)值之和。

---

解題思路

我們可以先計算一次點1為根時的答案，路上統(tǒng)計答案為didi，然后定義fifi為以i為根節(jié)點時的權(quán)值。
然后我們再由f1f1轉(zhuǎn)移到后面。我們考慮每一個子節(jié)點，
首先我們知道這個父節(jié)點轉(zhuǎn)移后價值是dxdx，然后原來的這個子節(jié)點的子樹，和其他的點都要和wiwi產(chǎn)生影響，具體轉(zhuǎn)移：

fy=dy+min{fx?min{dy,wi},wi}fy=dy+min{fx?min{dy,wi},wi}

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define N 200010 using namespace std; struct tree{int to,next,w; }a[2*N]; int n,in[N],w,ls[N],f[N],d[N],tot,rx,ry,ans,t; bool v[N]; void addl(int x,int y,int w) {a[++tot].to=y;a[tot].w=w;a[tot].next=ls[x];ls[x]=tot;in[y]++; } void dp(int x)//第一次計算 {v[x]=1;for(int i=ls[x];i!=-1;i=a[i].next){int y=a[i].to;if(v[y]) continue;dp(y);if(in[y]==1) d[x]+=a[i].w;else d[x]+=min(d[y],a[i].w);} } void dfs(int x){v[x]=1;for(int i=ls[x];i!=-1;i=a[i].next){int y=a[i].to;if(v[y]) continue;if(in[x]==1) f[y]=d[y]+a[i].w;else f[y]=d[y]+min(f[x]-min(d[y],a[i].w),a[i].w);dfs(y);} }//換根 int main() {scanf("%d",&t);while(t--){tot=0;memset(ls,-1,sizeof(ls));memset(f,0,sizeof(f));memset(d,0,sizeof(d));memset(v,0,sizeof(v));memset(in,0,sizeof(in));scanf("%d",&n);for (int i=1;i<n;i++){scanf("%d%d%d",&rx,&ry,&w);addl(rx,ry,w);addl(ry,rx,w);//連邊}dp(1);f[1]=d[1];ans=0;memset(v,0,sizeof(v));dfs(1);for(int i=1;i<=n;i++)ans=max(ans,f[i]);printf("%d\n",ans);} }

總結(jié)

以上是生活随笔為你收集整理的POJ3585-Accumulation Degree【树形dp,二次扫描与换根法】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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