树的直径

luckydrawbox · 2022-08-30 20:19:54 · 个人记录

两次DFS法

宏定义

变量

函数

代码

#define T_D_T int
struct Tree_Diameter{
    int s,t;
    T_D_T d[N],len;
    void init(){
        s=t=0;
        len=0;
        memset(d,0,sizeof(d));
    }
    void dfs(int x,int fa){
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            T_D_T z=edge[i];
            if(y==fa)
                continue;
            d[y]=d[x]+z;
            if(d[y]>d[s])
                s=y;
            dfs(y,x);
        }
    }
    void calc(){
        init();
        dfs(1,0);
        d[t=s]=0;
        dfs(s,0);
        len=d[s];
    }
}tree;

树形DP法

宏定义

变量

函数

代码

#define T_D_T int
struct Tree_Diameter{
    T_D_T d1[N],d2[N],len;
    void init(){
        len=0;
        memset(d1,0,sizeof(d1));
        memset(d2,0,sizeof(d2));
    }
    void dfs(int x,int fa){
        d1[x]=d2[x]=0;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            T_D_T z=edge[i];
            if(y==fa)
                continue;
            dfs(y,x);
            int t=d1[y]+z;
            if(t>d1[x]){
                d2[x]=d1[x];
                d1[x]=t;
            }
            else if(t>d2[x])
                d2[x]=t;
        }
        len=max(len,d1[x]+d2[x]);
    }
    void calc(){
        init();
        dfs(1,0);
    }
}tree;