poj2631 树的直径(两次bfs/树形dp)

题意

求树的直径，即树上最长的一条路

题解

①两次bfs

②两次dfs，期间更新最大值

③树形dp，因为一个分支节点只能从三个方向更新，最大的那两个方向之和就是该点的最长距离

思路来源及证明部分

http://hzwer.com/2996.html

https://www.cnblogs.com/a-clown/p/6131346.html

代码

①树形dp

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=2e6+10;
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std; 
struct edge
{
	int to,nex,w;
}e[maxn]; 
int head[maxn],cnt; 
//dp[u][0]代表最长
//dp[u][1]代表次长
void add(int u,int v,int w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
int ans,dp[maxn][2]; 
void init()
{
	mem(head,-1);
	cnt=0;
}
void dfs(int u,int fa)
{
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].to,w=e[i].w;
		if(v==fa)continue;
		dfs(v,u);
		if(dp[v][0]+w>dp[u][0])
		{
			dp[u][1]=dp[u][0];
			dp[u][0]=dp[v][0]+w;
		}
		else dp[u][1]=max(dp[u][1],dp[v][0]+w);
	}
	ans=max(ans,dp[u][0]+dp[u][1]);
}
int main()
{ 
   int u,v,w;
   init();
   while(~scanf("%d%d%d",&u,&v,&w))
   add(u,v,w),add(v,u,w);
   dfs(1,-1);
   printf("%d\n",ans);
   return 0;
}

②两次dfs

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int maxn=2e6+10;
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<int,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std; 
struct edge
{
	int to,nex,w;
}e[maxn]; 
int head[maxn],cnt; 
void add(int u,int v,int w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
int to,tmp; 
void init()
{
	mem(head,-1);
	cnt=0;
}
void dfs(int u,int fa,int dis)
{
	if(dis>tmp)tmp=dis,to=u;
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].to,w=e[i].w;
		if(v==fa)continue;
		dfs(v,u,dis+w);
	}
}
int main()
{ 
   int u,v,w;
   init();
   while(~scanf("%d%d%d",&u,&v,&w))
   add(u,v,w),add(v,u,w);
   dfs(1,-1,0);
   tmp=0;
   dfs(to,-1,0);
   printf("%d\n",tmp);
   return 0;
}