维修道路(repair)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

由于在十多年前道路改建时的突出贡献， Bob 被任命为维修道路的承包商，他可以任意
选择两条路径去修理。
Bob 刚刚获悉，这 n 个村庄相互连通，而且总共只有 n-1 条边。
众所周知， Bob 修理这两条道路得到的获益是两条路径的长度的积，所以当然他想最大
化他的获益。
但是， Bob 又不希望别人在背后说他坏话，所以他希望这两条路径满足以下两个条件：
1. 这两条路径都是某两个村庄之间的最短路径。 (某两个村庄就是路径的起点和终点)
2. 这两条路径不会经过同一个村庄。

输入

第一行输入 n。表示村庄个数。
接下来 n-1 行，每行两个数，表示这两个村庄之间有一条无向边。

输出

输出获益的最大值。

样例输入

1 2

2 3

3 4

1 2

1 3

1 4

1 5

1 6

1 7

1 2

2 3

2 4

5 4

6 4

样例输出

提示

1.选择(1->2)和(3->4) Ans=1*1
2.不管怎么选择这两条路径，一定会经过 1
3.选择(1->3)和(5->6) Ans=2*2=4

emmmm
其实不难
题意：在一棵树上找到两条不相交的路径（不能有点重合），　并且是两点之间的最短路径
使这两个路径长度的乘积最大
可以发现，这两条在树上了路径，肯定是两个不同的部分中（因为他在树上qwq）
那我们就枚举断掉树的一条边，然后再分别求这两个树的直径就是最优的答案了。
这个是O(n^2)的
有两个点T掉了
怎么办呢
这个简单，直接打表优化awa
我们直接分类讨论，讨论直径是否断开，如果不断开，那么结果是直径长度与挂在直径下面的子树的直径乘积。
设直径的左右端点为A和B，断开直径的一条边，那么结果就是左边某个点到A的长度和右边某个点到B的长度，可以通过维护前缀的和后缀，分别维护左边到达A和右边到达B的最长路。
直接引用题解

qwq

这个代码没写awa

O(n^2)的有qwq
奉上

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,tot=1,flag1,flag2,head[1000001];
int sum,ret,ans,id;
struct edge
{
    int next,to;
}e[1000001];
inline ll read()
{
    char c=getchar();ll a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;
    return a*b;
}
inline void add(int i,int j)
{
    e[++tot].next=head[i];
    e[tot].to=j;
    head[i]=tot;
}
 void dfs(int x,int fa,int dis,int opt)
{
    if(opt==1&&x==flag2) return;
    if(opt==2&&x==flag1) return;
    if(dis>ret)ret=dis,id=x;
    for(int i=head[x];i!=0;i=e[i].next)
    {
        int u=e[i].to;
        if(u==fa)continue;
        dfs(u,x,dis+1,opt);
    }
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int x=read(),y=read();
        add(x,y);add(y,x);
    }
    for(int i=2;i<=tot;i+=2)
    {
        ret=0;sum=0;id=0;
        flag1=e[i].to;
        flag2=e[i^1].to;
        dfs(flag1,flag2,0,1);
        ret=0;
        dfs(id,flag2,0,1);
        sum=ret,ret=0,id=0;
        dfs(flag2,flag1,0,2);
        ret=0;
        dfs(id,flag1,0,2);
        sum*=ret;
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}