树的直径

一篇讲的比较好的文章

总的来说，如果直径只看边权的话，\(Dfs\)和\(DP\)要区分开来，\(Dfs\)不能处理负边权，而\(DP\)可以。

如果包含点权的话，建议\(Dfs\),可以方便的记录路径。

例题：\(APIO2010\)巡逻

很水，找两遍直径即可。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int f=1,w=0;char x=0;
    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
    return w*f;
}
const int N=200100;
map<int,int> PL;
int n,K,num_edge;
int head[N],fa[N],L[3],las[N],d[N];
struct Edge {int next,to,dis;} edge[N];
inline void Add(int from,int to,int dis)
{
    edge[++num_edge].next=head[from];
    edge[num_edge].dis=dis;
    edge[num_edge].to=to;
    head[from]=num_edge;
}
inline void dfs(int pos,int fa,int from)
{
    las[pos]=from;
    for(int i=head[pos];i!=-1;i=edge[i].next)
        if(edge[i].to!=fa&&!d[edge[i].to])
        {
            d[edge[i].to]=edge[i].dis+d[pos];
            dfs(edge[i].to,pos,i);
        }
}
inline void Find_Dia(int from)
{
    memset(d,0,sizeof(d));
    dfs(from,0,0);
    for(int i=1;i<=n;i++) if(d[i]>d[from]) from=i;
    memset(d,0,sizeof(d));memset(las,-1,sizeof(las));
    dfs(from,0,-1);int end=from;
    for(int i=1;i<=n;i++) if(d[i]>d[end]) end=i;L[1]+=d[end];
    while(las[end]!=-1)
        edge[las[end]].dis=-1,            edge[las[end]^1].dis=-1,            end=edge[las[end]^1].to;
}
inline void Find_DP(int pos,int fa)
{
    for(int i=head[pos];i!=-1;i=edge[i].next)
        if(edge[i].to!=fa)
        {
            Find_DP(edge[i].to,pos);
            L[2]=max(L[2],d[pos]+d[edge[i].to]+edge[i].dis);
            d[pos]=max(d[pos],d[edge[i].to]+edge[i].dis);
        }
}
int main(){
#ifndef ONLINE_JUDGE
    //freopen("A.in","r",stdin);//Ans=11;
    //freopen("B.in","r",stdin);//Ans=10;
    freopen("C.in","r",stdin);//Ans=6;
#endif
    n=read();K=read();
    memset(head,-1,sizeof(head));num_edge=-1;
    for(int i=1,u,v;i<n;i++)
        u=read(),v=read(),Add(u,v,1),Add(v,u,1);
    if(K==1) {Find_Dia(1),printf("%d",2*n-L[1]-1);return 0;}
    Find_Dia(1);memset(d,0,sizeof(d));
    Find_DP(1,0);
    printf("%d\n",2*n-L[1]-L[2]);
    /*printf("%d %d\n",L[1],L[2]);
    for(int i=1;i<=2*(n-1);i++)
    {
        printf("to:%d,dis:%d\n",edge[i].to,edge[i].dis);
        }*/
}

树的直径

原文：https://www.cnblogs.com/wo-shi-zhen-de-cai/p/11279208.html