树的直径两种求解方式(dfs,dp)

1.dfs

void dfs(int now,int fa,int weight)//now：起点，fa：now的父节点，weight：搜索到当前点的路径长度
{if(l<weight)//发现更大的长度，更新id与l{id=now;l=weight;}for(auto nxt:e[now])//对于每一个子节点{int v=nxt.v,w=nxt.w;if(v==fa)continue;dfs(v,now,weight+w);}return ;
}

先以任一点为起点进行一次搜索，搜索结束后的id为下一次搜索的起点，第二次搜索完成后，所得到的id与第一次的id之间的路径就是树的直径，长度为l。
两次dfs的优点是:可以记录直径的起点，再配合一个dfs可以求出直径上的每一个点。
求得路径上的每一个点：

void dfs(int now,int fa,int ed)//now为第一次得到的id，ed为第二次得到的id
{for(auto nxt:e[now]){int v=nxt.v;if(flag==1)return ;//如果已经找到了到达ed的路径，直接退出if(v==fa)continue;if(v==ed){flag=1;//找到终点，更新flag，告诉后面的直接退出。road[now]=ed;//路径记录return ;}road[now]=v;//路径记录dfs(v,now,ed);}return ;
}

缺点:无法解决负边权的情况。

dp

int dfs(int now,int fa)
{int d1=0,d2=0;//d1记录以now开始的最大长度，d2记录now开始的次大长度for(auto nxt:e[now]){int v=nxt.v,w=nxt.w;if(fa==v)continue;int d=dfs2(v,now)+w;//d为从以v为根节点的子树可以获得的最大长度if(d>d1){d2=d1,d1=d;}//根据d与d1，d2的大小关系进行更新else if(d>d2){d2=d;}l=max(l,d1+d2);//l记录整个树里面的最大直径}return d1;//返回最大以now为根节点的最大长度
}

优点:可以处理负边权的树。
缺点:只能求一个树的直径的长度，其他的求不出(起点，终点，路径)。