给出一棵树,要求给树的每条边赋权值,使得树中所有点的
m
e
x
(
x
,
y
)
mex(x,y)
mex(x,y)和最大,并输出这个和
m
e
x
(
x
,
y
)
mex(x,y)
mex(x,y)指的是从x到y的路径中,没出现过的整数的最小值
推荐qsc的题解视频:传送门
很容易发现,在这个条件下,一定要有人做出牺牲,也就是只有一条链上能够从小到大接连着,还可以发现的是,只要有一条边选择了0,那么这条边两头的点满足
m
e
x
(
x
,
y
)
≥
1
mex(x,y)\ge1
mex(x,y)≥1,因为他们中最小的整数为0,也就是对于这样的一条连着的整数链来说,比如0,1,2,这样的链两边的点形成的链值至少为3,这也就是这道题的精髓。
可以发现,这题n只有3000,所以支持n^2,那么就很美滋滋,刚才发现,从小到大接着的链非常重要,所以直接
n
2
n^2
n2枚举这条链。首先需要一个预处理,
f
a
[
r
o
o
t
]
[
u
]
fa[root][u]
fa[root][u]表示以root为根,u的父亲是谁,
n
u
m
[
r
o
o
t
]
[
u
]
num[root][u]
num[root][u]表示以root为根,以u为顶点的子树有多少点。然后使用
d
p
[
x
]
[
y
]
dp[x][y]
dp[x][y]来表示x,y为链的情况下的最大值是多少。如何dp呢?假设求1-2-3-4这样的链的结果,那么假如我们已经知道了它的子结果,1-2-3和2-3-4的结果,我们要从这个结果推出1-2-3-4结果,那么根据我们的分析,从1-2-3和2-3-4变成1-2-3-4都是加上1-2-3-4这条链两头点的乘积(就是这棵树中有多少条链能够覆盖这条链,他们都能得到这个加成),既然加的数值一样,那么肯定选他们两个中大的那个啦。数量的话很简单,对于x-…-y这条链来说,x那边的点的个数就是以y为根,x为子树顶点的子树的点数量,另一边就正好相反,就是刚才说的
n
u
m
[
r
o
o
t
]
[
u
]
num[root][u]
num[root][u]可以得到,而1-2-3和2-3-4的获得,就可以用
f
a
[
r
o
o
t
]
[
u
]
fa[root][u]
fa[root][u],同样对于x-…-y这条链来说,
f
a
[
x
]
[
y
]
fa[x][y]
fa[x][y]就是x-…-y这条链中,与y直接相连的那个点。
感觉这题非常巧妙,有很多可以学习的点,是一个好题。感觉讲的已经比较清楚,代码也比较剪短可以结合代码学习。如果还有有问题的地方欢迎评论区提出一起讨论~
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define inf 0x3f3f3f3f
const int MAXN = 3e3+5;
vector<int>v[MAXN];
ll fa[MAXN][MAXN],num[MAXN][MAXN],dp[MAXN][MAXN],root;
void dfs(int u,int f){
num[root][u]=1;
int len=v[u].size();
rep(i,0,len-1){
int y=v[u][i];
if(y==f)continue;
fa[root][y]=u;
dfs(y,u);
num[root][u]+=num[root][y];
}
}
ll solve(int x,int y){
if(x==y)return 0;
if(dp[x][y])return dp[x][y];
return dp[x][y]=num[x][y]*num[y][x]+max(solve(x,fa[x][y]),solve(y,fa[y][x]));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,x,y;
while(cin>>n){
rep(i,1,n)v[i].clear();
memset(fa,0,sizeof(fa));
memset(num,0,sizeof(num));
memset(dp,0,sizeof(dp));
rep(i,1,n-1){
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
rep(i,1,n){
root=i;
dfs(i,-1);
}
ll ans=0;
rep(i,1,n){
rep(j,i+1,n){
ans=max(ans,solve(i,j));
}
}
cout<<ans<<endl;
}
return 0;
}