正題

題目鏈接:https://gmoj.net/senior/#main/show/4279

---

題目大意

$n$個點的一棵樹求經(jīng)過每個點的最長路徑。

---

解題思路

設(shè)$f_i$表示$i$子樹內(nèi)的最長路徑。

我們第二次轉(zhuǎn)移一個位置時我們枚舉除了這個子樹之外的其他子樹，找到之外最大的$f_i$轉(zhuǎn)移下去即可。

因為數(shù)據(jù)保證了不會有菊花圖所以能過

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e5+10; struct node{ll to,next,w; }a[N*2]; ll n,tot,ls[N],f[N],g[N]; void addl(ll x,ll y,ll w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot;return; } void dfs(ll x,ll fa){f[x]=0;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;dfs(y,x);f[x]=max(f[x],f[y]+a[i].w);}return; } void dp(ll x,ll fa,ll maxs){g[x]=f[x]+maxs;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==fa)continue;ll z=maxs;for(ll j=ls[x];j;j=a[j].next)if(a[j].to!=fa&&a[j].to!=y){z=max(z,f[a[j].to]+a[j].w);g[x]=max(g[x],f[y]+f[a[j].to]+a[i].w+a[j].w);}dp(y,x,z+a[i].w);}return; } int main() {freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);scanf("%lld",&n);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);}dfs(1,1);dp(1,1,0);for(ll i=1;i<=n;i++)printf("%lld\n",g[i]); }

總結(jié)

以上是生活随笔為你收集整理的jzoj4279-[NOIP2015模拟10.29B组]树上路径【树形dp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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