思路：我們其實只需要枚舉每條邊，求得最小值就行了。

先dfs算出每個節點作為根時，其子樹的最長路徑，以及進過該節點的最長，次長，第三長路徑。

然后在次dfs枚舉求出切斷某條邊，求出這條邊的兩個端點為子樹根，其子樹的最長路徑。b就是其中較大的。

#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #include<vector> #define Maxn 200010 using namespace std; int road[Maxn],Max[Maxn],lMax[Maxn],vi[Maxn],e,head[Maxn],dis[Maxn],ldis[Maxn],pr,ans,sMax[Maxn],lroad[Maxn]; struct Edge{int u,v,val,id,next; }edge[Maxn*4]; void init() {memset(road,0,sizeof(road));memset(Max,0,sizeof(Max));memset(lMax,0,sizeof(lMax));memset(vi,0,sizeof(vi));memset(dis,0,sizeof(dis));memset(ldis,0,sizeof(ldis));memset(head,-1,sizeof(head));memset(sMax,0,sizeof(sMax));memset(lroad,0,sizeof(lroad));e=0; } void add(int u,int v,int val,int id) {edge[e].u=u,edge[e].v=v,edge[e].val=val,edge[e].id=id,edge[e].next=head[u],head[u]=e++;edge[e].u=v,edge[e].v=u,edge[e].val=val,edge[e].id=id,edge[e].next=head[v],head[v]=e++; } void dfs(int u) {int i,v;vi[u]=1;for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;if(vi[v]) continue;dfs(v);if(Max[v]+1>Max[u]){sMax[u]=lMax[u];lroad[u]=road[u];lMax[u]=Max[u];Max[u]=Max[v]+1;road[u]=v;}elseif(Max[v]+1>lMax[u]){sMax[u]=lMax[u];lMax[u]=Max[v]+1;lroad[u]=v;}dis[u]=max(dis[u],Max[u]+lMax[u]);dis[u]=max(dis[u],dis[v]);} } void predfs(int u,int d,int pre,int fa) {int i,v;vi[u]=1;int now=0;int a,b=0;for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;if(vi[v]) continue;a=edge[i].val;now=pre;if(road[u]==v){now=max(d+lMax[u],now);now=max(lMax[u]+sMax[u],now);b=max(now,dis[v]);if(a*b<=pr){if(a*b==pr){if(edge[i].id<ans)ans=edge[i].id;}elsepr=a*b,ans=edge[i].id;}predfs(v,max(d,lMax[u])+1,now,u);}elseif(lroad[u]==v){now=max(d+Max[u],now);now=max(Max[u]+sMax[u],now);b=max(now,dis[v]);if(a*b<=pr){if(a*b==pr){if(edge[i].id<ans)ans=edge[i].id;}elsepr=a*b,ans=edge[i].id;}predfs(v,max(d,Max[u])+1,now,u);}else{now=max(d+Max[u],now);now=max(Max[u]+lMax[u],now);b=max(now,dis[v]);if(a*b<=pr){if(a*b==pr){if(edge[i].id<ans)ans=edge[i].id;}elsepr=a*b,ans=edge[i].id;}predfs(v,max(d,Max[u])+1,now,u);}} } int main() {int n,i,j,m,t,u,v,w,Case=0;scanf("%d",&t);while(t--){init();scanf("%d",&n);for(i=1;i<=n-1;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w,i);}int a,b;dfs(1);memset(vi,0,sizeof(vi));pr=2000000000;ans=10000000;predfs(1,0,0,0);printf("Case #%d: %d\n",++Case,ans);}return 0; }

?

?

轉載于:https://www.cnblogs.com/wangfang20/p/3262308.html

總結

以上是生活随笔為你收集整理的hdu 4679 树状dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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