题目链接
题目大意:
给一棵(n)个节点的树,将([0,n-2])分配到每一条边,定义(s(s,t))为(s)到(t)路径边权的(mex),求(s(s,t))和的最大值
名词解释:(mex):没有出现的最小自然数(即([0,+infty]))
题目思路:
emm,感觉假如这棵树变为一条链的情况可以讨论一下,对本题有启发。(其实就是链上方案推广到树上,两者是相通的。但链的情况显然更好想)
先考虑 (0) 的放置,根据定义,若 (0) 放置在一条左边有 (x) 节点,右边有 (y) 节点的边,则贡献为 (x imes y),最大化该值即可。
再考虑 (1) 的放置,若 (1) 不在 (0) 边的左或右,方案将不会更优。证明如下。
现有两个方案
A:.... 2 1 0 ..... B: .... 1 2 0 ....
假设...
并没有差别,那么
-
按照题意,不考虑 (0) 左右的内部答案,因为都是 (0)
-
左边的...到右边的...答案没有差别
-
(1) 到右边的...,B答案>A答案(全是 (2))
-
(2) 到右边的...,A答案>B答案(全是 (1))
显然,(2) 中的B答案等于 (3) 中的A答案,即两方案的答案事实上是相同的,若考虑将上文方案中的 (2) 换为大于 (2) 的数,则B显然会比A劣。因此,(1) 须放在 (0) 的左右。具体的说,若 (0) 左边有 (x) 个节点,右边有 (y) 个节点,那么需比较 ((x-1) imes y) 和 (x imes (y-1))。
接着往下考虑,可以证明对于每个数,使该数在已编号的序列的左、右将不会更劣。方案亦与上文类似。
其实,我们可以看到,每个边对答案的贡献是经过该边的次数 ( imes 1 /0) 。即只有两种情况。因此,我们在按照上面的构造方案的情况下无需再考虑编号问题。
按上面的方法,一条链的方案便可构造出来。
分割线
回到正文,现在我们考虑的是树,但可以视为若干条链。如上文所说,链和树的做法里某些东西是相通的。
仿照链的做法,此时放置方案应使 (0) 到一个尽量大的数都放在一条特定的链上。其他方案不会更优。至于证明,可仿照链的证明方式。
那么现在我们要找到这条特定的链。通过贪心来找到这条特定的链不大可行。考虑每一条链都求出该链为特定链时,这棵树的总答案。
这里可以通过记忆化搜索求解,通过 ((u,v)) 的答案可求 (u),(v) 的子节点的答案。
记 (f(u,v)) 为将 (u) 到 (v) 作为上文的特定的链的答案。则
(f(u,v)=max(f(fa_u,v),f(i,fa_v))+siz_u imes siz_v)。
但是,随着 ((u,v)) 的改变,树的形态可能会发生一定改变,这意味着 (fa_x) 和 (siz_x) 会发生改变,解决方案是将每个节点作根时的(fa)和(siz)状况都预处理下来,在 ((u,v)) 状况下,(fa_u) 和 (siz_u) 分别是 (v) 作为根时的 (fa) 和 (siz),这个画图可以理解。
至此,本题基本完成,以下是本题代码。
#include<bits/stdc++.h>
using namespace std;
int cc,to[6000],net[6000],fr[6000];bool vis[6000];
int rot,fa[3005][3005];
int n,u,v;long long ans,f[3005][3005],siz[3005][3005];
void addedge(int u,int v)
{
cc++;
to[cc]=v;net[cc]=fr[u];fr[u]=cc;
}
void dfs(int x)
{
vis[x]=true;
for (int i=fr[x];i;i=net[i])
{
if (!vis[to[i]])
{
fa[rot][to[i]]=x;
siz[rot][to[i]]=1;
dfs(to[i]);
siz[rot][x]+=siz[rot][to[i]];
}
}
}
long long dp(int u,int v)
{
if (f[u][v]) return f[u][v];
if (u==v) return 0;
f[u][v]=max(dp(fa[v][u],v)+siz[v][u]*siz[u][v],
dp(u,fa[u][v])+siz[v][u]*siz[u][v]);
return f[u][v];
}
int main()
{
cin>>n;
for (int i=1;i<n;i++)
{
cin>>u>>v;
addedge(u,v);
addedge(v,u);
}
for ( rot=1;rot<=n;rot++)
{
for (int j=1;j<=n;j++)
vis[j]=false;
siz[rot][rot]=1;fa[rot][rot]=0;dfs(rot);
}//预处理每个节点为根时的fa和siz
for (int i=1;i<=n;i++)
for (int j=1;j<n;j++)
{
dp(i,j);ans=max(ans,f[i][j]);
}//记搜
cout<<ans<<endl;
return 0;
}