构造边权, 从 0 开始给边赋值, 初始选取一条边权为 0, 每次赋值的贡献为这一条链两侧的结点 (包含链的端点) 个数之积, 下一次赋值以当前链其一端点续一条边, 边权为上次赋的值 + 1. 先 DFS 找到点的组合这条链两侧结点的个数(包含链的端点), 然后枚举端点进行 DP.
- #define HAVE_STRUCT_TIMESPEC
- #include<bits/stdc++.h>
- using namespace std;
- vector<long long>edge[3007];
- long long cnt[3007][3007];
- long long fa[3007][3007];
- long long dp[3007][3007];
- void dfs(long long now,long long f,long long root){
- cnt[root][now]=1;// 链的起点与当前点相反的一侧的结点个数(包括链的端点)
- fa[root][now]=f;// 当前点与链的起点相同的一侧的父节点为 f
- for(auto it:edge[now]){
- if(it==f)
- continue;
- dfs(it,now,root);
- cnt[root][now]+=cnt[root][it];// 将结果回溯到上层结点
- }
- }
- long long solve(long long l,long long r){// 求以 l 和 r 作为链的端点的答案最大值
- if(l==r)// 起点与终点不能相同
- return 0;
- if(dp[l][r]==0)//l 和 r 第一次作为链的两端
- dp[l][r]=cnt[l][r]*cnt[r][l]+max(solve(l,fa[l][r]),solve(r,fa[r][l]));// 这一段的结果为链两端结点个数 (包括链的段点) 乘积加上当前链去掉一个端点的答案(两个端点其一为新加入的点, 新边的权值为原链中边的权值最大值 + 1)
- return dp[l][r];
- }
- int main(){
- iOS::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- long long n;
- cin>>n;
- for(long long i=1;i<n;++i){
- long long u,v;
- cin>>u>>v;
- edge[u].emplace_back(v);
- edge[v].emplace_back(u);
- }
- for(long long i=1;i<=n;++i)// 枚举链的起点
- dfs(i,-1,i);// 深搜
- long long ans=0;
- for(long long i=1;i<=n;++i)// 枚举链的起点
- for(long long j=1;j<=n;++j)// 枚举链的终点
- ans=max(ans,solve(i,j));
- cout<<ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3394635.html