Light OJ 1094 - Farthest Nodes in a Tree

传送门

思路：树的直径。

方法1：两次$bfs$，第一次找到直径的一个端点，然后再从该端点$bfs$一次的最大距离即为直径，$bfs$方法需要用一个数组$d$维护距离和判断是否在队列中。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e4+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define fmst(a) memset(a,-1,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int d[N],h[N],cnt,n; //数组d两个作用，记录距离和标记是否在队列中. struct edge{ int to,nt,w; }e[N<<1]; void add(int u,int v,int w){ e[++cnt]={v,h[u],w},h[u]=cnt; } void bfs(int s){ fmst(d),d[s]=0; queue<int>q; q.push(s); while(!q.empty()){ int u=q.front();q.pop(); for(int i=h[u];i;i=e[i].nt){ int v=e[i].to,w=e[i].w; if(!~d[v]) d[v]=d[u]+w,q.push(v); } } } int main(){ int t; scanf("%d",&t); for(int k=1;k<=t;k++){ mst(h),cnt=0;//初始化. scanf("%d",&n); for(int i=1,u,v,w;i<n;i++){ scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w); } int mx=0,p=0; bfs(0); for(int i=0;i<n;i++) if(d[i]>mx) mx=d[i],p=i; bfs(p); for(int i=0;i<n;i++) if(d[i]>mx) mx=d[i]; printf("Case %d: %d\n",k,mx); } return 0; }

方法2：两次$dfs$思路同理。

证明方法的思路是：讨论开始搜的起点$p$是否为直径的端点，若是显然为直径，

若不是再分别讨论，用反证法，假设$pq$不是直径，讨论$pq$与直径$ab$是否有交点。

具体证明见别人的博客，不想写了。

$dfs$方法不需要用数组$d$维护，直接在$dfs$里求最大距离即可，因为$dfs$每个点只会遍历一次，当前距离一定是最短距离(因为是一棵树，而不是图，不需要比较距离）。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e4+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a) memset(a,0,sizeof a) #define fmst(a) memset(a,-1,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second int h[N],cnt,n,pos,ans; struct edge{ int to,nt,w; }e[N<<1]; void add(int u,int v,int w){ e[++cnt]={v,h[u],w},h[u]=cnt; } void dfs(int u,int fa,int d){ if(d>ans) ans=d,pos=u; for(int i=h[u];i;i=e[i].nt){ int v=e[i].to,w=e[i].w; if(v==fa) continue; dfs(v,u,d+w); } } int main(){ int t; scanf("%d",&t); for(int k=1;k<=t;k++){ mst(h),cnt=0;//初始化. scanf("%d",&n); for(int i=1,u,v,w;i<n;i++){ scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w); } ans=0,pos=0; dfs(0,-1,0); dfs(pos,-1,0); printf("Case %d: %d\n",k,ans); } return 0; }

方法3：树形$dp$. 待补。