树的直径

　　noip 2018 day1 t3听学长说是二分+树形dp+二分。但是暴力分给的还是挺足的55分。

20分是树的直径，无奈不会求，n^n暴力dfs只拿了10分，血亏一波。

1.树形dp求树的直径

设当前节点为x,d[x]表示以x为节点所能到达的最长链。显然对于穿过x的树的直径=d[x]+d[tn]+e(x,tn);

这样直接一遍dp即可。

void dp(long long x)
{    
    vis[x]=1;
    for(long long i=lin[x];i;i=nex[i])
    {
        long long tn=ver[i];
        if(vis[tn]==1)continue;
        dp(tn);
        cnt=max(cnt,d[x]+d[tn]+e[i]);
        d[x]=max(d[x],d[tn]+e[i]);
    }
    return;
}
//cnt 即为答案

2.通过两遍dfs或bfs来求树的直径。

先任取一个点求出距离此点最远的距离的点，然后从这个点在跑出距离当前点最远的点即可。

我觉得不是很显然，当然也不会证，画出不同种的情况来显然一下吧。

dfs:

    for(int i=lin[x];i;i=nex[i])
    {
        int tn=ver[i];
        if(vis[tn]==1)continue;
        vis[tn]=1;
        d[tn]=max(d[tn],d[x]+e[i]);
        if(d[tn]>cnt)cnt=d[tn],u=tn;
        dfs(tn);
    }
        cnt=0;vis[1]=1;dfs(1);
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    cnt=0;vis[u]=1;dfs(u);
    put(cnt);

bfs也是相同的道理。

h=0,t=0;cnt=0;
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    q[++t]=1;vis[1]=1;
    while(h++<t)
    {
        long long te=q[h];
        for(long long i=lin[te];i;i=nex[i])
        {
            long long tn=ver[i];
            if(vis[tn]==1)continue;
            d[tn]=max(d[tn],d[te]+e[i]);//取max更加严谨,尽管更慢
            if(d[tn]>cnt)cnt=d[tn],u=tn;
            q[++t]=tn;vis[tn]=1;
        }
    }
    //cout<<u<<endl;
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    h=0,t=0;cnt=0;
    q[++t]=u;vis[u]=1;
    //cout<<u<<endl;
    while(h++<t)
    {
        long long te=q[h];
        for(long long i=lin[te];i;i=nex[i])
        {
            long long tn=ver[i];
            if(vis[tn]==1)continue;
            d[tn]=max(d[tn],d[te]+e[i]);//取max更加严谨,尽管更慢
            if(d[tn]>cnt)cnt=d[tn];
            q[++t]=tn;vis[tn]=1;
        }
    }
    put(cnt);return;

dfs，bfs便利两次可能常数较大，但是可以求出一些关键点的信息，如直径的两端等等。

很简单的东西。