首页 > 代码库 > hdu 3534 Tree(树形DP)

hdu 3534 Tree(树形DP)

2024-09-06 05:54:45   218人阅读

题目链接：hdu 3534 Tree

题意：

给你一棵n个节点,n-1条边的树，每条边有一个长度，现在问你最长的边的长度为多少，有多少条。

题解：

其实这种题不用记录最长和次长，我们开两个数组，len[i]，num[i]。

表示以i为根结点出发的最长的长度以及最长的边的条数。

然后我们只需要一个dfs，先用子节点的信息来更新答案，然后在更新当前节点的len和num记录的信息。

这样就不用记录最长和次长。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=a;i<=b;++i)
 4 using namespace std;
 5 typedef long long ll;
 6 
 7 const int N=1e4+7;
 8 
 9 int g[N],v[N*2],nxt[N*2],w[N*2],ed;
10 int n,ans,k,len[N],num[N];
11 
12 void adg(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;}
13 
14 void dfs(int x,int fa)
15 {
16     len[x]=0,num[x]=1;
17     for(int i=g[x];i;i=nxt[i])if(v[i]!=fa)
18     {
19         dfs(v[i],x);
20         int tmp=w[i]+len[v[i]];
21         if(tmp+len[x]>ans)ans=tmp+len[x],k=num[x]*num[v[i]];
22         else if(tmp+len[x]==ans)k+=num[x]*num[v[i]];
23         if(tmp>len[x])len[x]=tmp,num[x]=num[v[i]];
24         else if(tmp==len[x])num[x]+=num[v[i]];
25     }
26 }
27 
28 int main(){
29     while(~scanf("%d",&n))
30     {
31         mst(g,0),ed=0;
32         int x,y,z;
33         F(i,1,n-1)
34         {
35             scanf("%d%d%d",&x,&y,&z);
36             adg(x,y,z),adg(y,x,z);
37         }
38         ans=-INT_MAX,k=0;
39         dfs(1,0),printf("%d %d\n",ans,k);
40     }
41     return 0;
42 }
View Code

 

hdu 3534 Tree(树形DP)


联系
我们