解释 :
求树的最长路(树的直径)
首先假设树的最长路的两个叶子节点为v1,v2，那么现有结论，从任意一点u出发走到的最远的点一定是（v1,v2）中的一点，然后
再从v1或者v2出发走到的最远点一定是v2或者v1。所以经过两次搜索就能找到最长路径.
相关证明
AC代码:
dfs 找节点
#include<cstdio>
#include<vector>
#include<cstring>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int maxn=1e5+5;
int dep[maxn];
int max_len,root,n;
int vis[maxn];
vector<int>ve[maxn];
int dfs(int x,int len)
{
vis[x]=1;
if(len >max_len) max_len=len,root=x;
for(int i=0;i<ve[x].size();i++){
if(!vis[ve[x][i]]){
dfs(ve[x][i],len+1);
}
}
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int u,v;
scanf("%d%d",&u,&v);
ve[u].push_back(v);
ve[v].push_back(u);
}
max_len=0;
CLR(vis);
dfs(1,0); //找到叶子结点之一,也许是最远.
CLR(vis);
dfs(root,0); //以一个叶子结点开始搜素,则搜出来的长度一定是最长.
printf("%d\n",max_len); //输出长度.
}
下面有一道这道题的加强版. (这道题读懂了的话还是可以敲的,就是我读题老是喜欢去抠字眼,其实不太懂时想想另一种说法, 问问自己这种说法是不是也可以符合题目的意思.所以真的要灵活点啊!!!,所以那次比塞真的是我的锅.)
地址
AC代码:
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn=1e5+5;
const db eps=1e-6;
const int inf=1e9;
const ll INF=1e15;
struct node
{
int to,next,w;
}s[maxn*2]; //无向边, 所以需要开大两倍.
int head[maxn];
int ans=0;
void add(int u,int to,int w)
{
s[ans].to=to;
s[ans].w=w;
s[ans].next=head[u];
head[u]=ans++;
}
ll dis1[maxn],dis2[maxn];
int vis[maxn];
void dfs(int x,ll len,ll *dis) //搜素这棵树的直径.
{
dis[x]=len;
vis[x]=1;
for(int i=head[x];i!=-1;i=s[i].next){
if(!vis[s[i].to])
dfs(s[i].to,len+s[i].w,dis);
}
}
int main()
{
int n;
while(~scanf("%d",&n)){
CLR(dis1);
CLR(dis2);
CLR(s);
memset(head,-1,sizeof(head));
ans=0;
for(int i=0;i<n-1;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); //加边.
add(v,u,w);
}
CLR(vis);
dfs(1,0,dis1); //以任意一个点去搜索, 搜出来最远的那个点一定是直径中的其中一个点.
int S=0,T=0;
ll maxx=0;
for(int i=1;i<=n;i++){
if(dis1[i]>maxx){
maxx=dis1[i];
S=i; //其中一个点.
}
}
CLR(vis);
dfs(S,0,dis1); //在以这个点去搜索, 最远的那个点就是直径中的另一个点.
maxx=0;
for(int i=1;i<=n;i++){
if(dis1[i]>maxx){
maxx=dis1[i];
T=i;
}
}
//printf("%d %d\n",S,T);
CLR(vis);
dfs(T,0,dis2);
ll res=dis1[T]; //先连接直径.
/*for(int i=1;i<=n;i++){
printf("%d ",dis1[i]);
}
printf("\n");*/
for(int i=1;i<=n;i++){
if(i == S || i == T) continue;
res += max(dis1[i],dis2[i]); //剩余每个点都选择里其本身比较远的那个点.
}
printf("%I64d\n",res);
}
}
我居然再一次败在long long 上面, 下次要用ll是我全部用ll了.!!!
