TTTTTTTTTTTTT 树的直径 Codeforces Beta Round #14 (Div. 2) D. Two Paths

tiyi:给你n个节点和n-1条边（无环），求在这个图中找到 两条路径，两路径不相交，求能找的两条路径的长度的乘积最大值；

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <queue>

#include <stack>

#include <map>

#include <algorithm>

#include <set>

using namespace std;

typedef long long ll;

typedef unsigned long long Ull;

#define MM(a,b) memset(a,b,sizeof(a));

const double eps = 1e-10;

const int inf = 0x3f3f3f3f;

const double pi=acos(-1);

const int mod=100000000;

ll max(ll a,ll b)

{return a>b?a:b;};

int min(int a,int b)

{return a<b?a:b;};

struct Edge{

  int u,v;

}e[205];

vector<int> G[205];

int vis[205],step[205],s,len;

int bfs(int a,int pre)

{

    int s=a;

    len=0;

    MM(vis,0);

    MM(step,0);

    queue<int> q;

    q.push(a);

    vis[pre]=vis[a]=1;

    while(q.size())

    {

        int u=q.front();q.pop();

        for(int i=0;i<G[u].size();i++)

        {

            int v=G[u][i];

            if(vis[v]) continue;

            q.push(v);

            vis[v]=1;

            step[v]=max(step[v],step[u]+1);

            if(step[v]>len)

            {

                len=step[v];

                s=v;

            }

        }

    }

    return s;

}//求树的直径len模板

int main()

{

    int n,u,v;

    while(~scanf("%d",&n))

    {

       for(int i=1;i<=n;i++) G[i].clear();

       for(int i=1;i<n;i++)

       {

           scanf("%d %d",&e[i].u,&e[i].v);

           G[e[i].u].push_back(e[i].v);

           G[e[i].v].push_back(e[i].u);

       }

       int ans=0;

       for(int i=1;i<n;i++)

       {

           int u=e[i].u,v=e[i].v;

           bfs(bfs(u,v),v);

           int x=len;

           bfs(bfs(v,u),u);

           x*=len;

           ans=max(ans,x);

       }

       printf("%d\n",ans);

    }

    return 0;

}

　　分析：枚举每条边，将图拆成两棵树（保证没有交点），分别求得两棵树的直径，乘积就是此时的最大值

树的直径资料：链接