CodeForces

题目链接：点击这里

题目大意：
给出一颗有 n n n 个节点的数，将 [ 0 , n − 2 ] [0,n-2] [0,n−2] 内的每个整数各用一次分配到这颗树的 n − 1 n-1 n−1 条边上，求 ∑ 1 ≤ i < j ≤ n m e x ( i , j ) \sum_{1\le i<j\le n}mex(i,j) ∑1≤i<j≤n​mex(i,j) 的最大值，其中 m e x ( i , j ) mex(i,j) mex(i,j) 指的是从 i i i 到 j j j 的路径上没有出现的最小非负数。

题目分析：
我们考虑从样例二分析，样例二的构造方案如图所示：

我们先考虑 0 0 0 的情况贡献：由于左边有 1 , 2 , 4 1,2,4 1,2,4 这 3 3 3 个点，右边有 3 , 5 3,5 3,5 两个点，故贡献为 0 ∗ 3 ∗ 2 0*3*2 0∗3∗2
设 m e x = v a l mex=val mex=val ，链左边有 l x lx lx 个点，右边有 r x rx rx 个点，不难发现，我们贡献就是 v a l ∗ l x ∗ r x val*lx*rx val∗lx∗rx
我们从易到难的想，先思如果树为一条链时如何处理：
定义状态 d p [ i ] [ j ] ( i < j ) dp[i][j](i<j) dp[i][j](i<j) 表示以 i , j i,j i,j 为端点链用从 0 0 0 开始的连续自然数赋值时的题目所求答案是多少，设 l c n t [ i ] lcnt[i] lcnt[i] 表示 i i i 左边有多少个点， r c n t [ i ] rcnt[i] rcnt[i] 表示 i i i 右边有多少个点
故有转移方程：
d p [ i ] [ j ] = l c n t [ i ] ∗ r c n t [ j ] + m a x ( d p [ i + 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j]=lcnt[i]*rcnt[j]+max(dp[i+1][j],dp[i][j-1]) dp[i][j]=lcnt[i]∗rcnt[j]+max(dp[i+1][j],dp[i][j−1])
而由于 n n n 只有 3000 3000 3000 ，所以我们就可以 O ( n 2 ) O(n^2) O(n2) 枚举端点，然后处理链的贡献，为了避免状态被重复计算，所以采用记忆化的方式进行 d p dp dp ，这样就保证了 d p dp dp 的复杂度为 O ( n 2 ) O(n^2) O(n2)
当在树上处理链时，我们需要预处理 f a [ x ] [ y ] , c n t [ x ] [ y ] fa[x][y],cnt[x][y] fa[x][y],cnt[x][y] ，其分别表示以 x x x 为根时 y y y 的父节点是谁，以 x x x 为根时 以 y y y 为根的子树大小，这样状态转移方程就可以写成：
d p [ x ] [ y ] = c n t [ y ] [ x ] ∗ c n t [ x ] [ y ] + m a x ( d p [ f a [ y ] [ x ] ] [ y ] , d p [ f a [ x ] [ y ] ] [ x ] ) dp[x][y] = cnt[y][x]*cnt[x][y]+max(dp[\ fa[y][x]\ ][y],dp[\ fa[x][y]\ ][x]) dp[x][y]=cnt[y][x]∗cnt[x][y]+max(dp[ fa[y][x] ][y],dp[ fa[x][y] ][x])

具体细节见代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define int ll
using namespace std;
int read()
{int res = 0,flag = 1;char ch = getchar();while(ch<'0' || ch>'9'){if(ch == '-') flag = -1;ch = getchar();}while(ch>='0' && ch<='9'){res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';ch = getchar();}return res*flag;
}
const int maxn = 3e3+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
int n,fa[maxn][maxn],dp[maxn][maxn],cnt[maxn][maxn];
vector<int>g[maxn];
void dfs(int u,int f,int root)
{cnt[root][u] = 1;fa[root][u] = f;for(auto to:g[u]){if(to == f) continue;dfs(to,u,root);cnt[root][u] += cnt[root][to];}
}
int solve(int x,int y)
{if(x == y) return 0;if(dp[x][y] != -1) return dp[x][y];dp[x][y] = cnt[y][x]*cnt[x][y]+max(solve(fa[y][x],y),solve(fa[x][y],x));return dp[x][y];
}
signed main()
{n = read();for(int i = 1;i < n;i++){int from = read(),to = read();g[from].push_back(to);g[to].push_back(from);}for(int i = 1;i <= n;i++) dfs(i,0,i);int ans = 0;memset(dp,-1,sizeof(dp));for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++) ans = max(ans,solve(i,j));cout<<ans<<endl;return 0;
}