一看到这道题我就是大写的懵逼
因为上半年去华科还是地大打邀请赛的时候做过类似的题目,当初是写不来的 结果现在……………………还是写不来………………造孽啊

题意:
给你一个无向不成环的图 让你找出两条不相交的树链 使其乘积最大

思路 :
枚举每一条道路 并使其暂时断裂 再从这条道路的两端开始搜索 寻找最长的树链即可
说实话 搜索的题目虽然说做的还凑合 但是这种给你一个连通方式 并以此形成无向图 再加以搜索的题目我还是第一次做
我先想得是用二维矩阵保存路径 以G[u][v] 表示从 u到v是连通的 再用vector省点空间
之后我较为习惯的用了BFS 然后就进入了无限懵逼崩溃懵逼崩溃的状态 说到底用矩阵保存如果不用上结构体的话 很难记录链长
无奈还是写了DFS

AC Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;
const int maxn=220;
bool vis[maxn];
vector<int> G[maxn];
int ans;

int dfs(int v,int x)
{
    int sum=0;
    int max1=0,max2=0;
    for(int i=0; i<G[v].size(); i++)
    {
        if(G[v][i]!=x)
        {
            sum=max(sum,dfs(G[v][i],v));//sum得到从一个NODE出发的树的直径   循环操作得到最大
                                        //与此同时 ans也在计算着从改点出发的最长树链
            if(ans>max1)
            {
                max2=max1;
                max1=ans;
            }
            else max2=ans>max2?ans:max2;
        }
    }
    sum=max(sum,max1+max2);//最后sum得到从V出发的树的直径
    ans=max1+1;//max1为该node的最长树链  因为递归返回  最大树链长度+1
    return sum;
}

int main()
{
    int n,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<=n; i++) G[i].clear();
        for(int i=0; i<n-1; i++)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        int last_ans=0;
        for(int i=0; i<n; i++)
        {
            int num=G[i].size(),temp;
            for(int j=0; j<num; j++)
            {
                int ans=0;
                temp=dfs(i,G[i][j])*dfs(G[i][j],i);
                last_ans=max(last_ans,temp);
            }
        }
        printf("%d\n",last_ans);
    }
    return 0;
}