题解 CF1292C 【Xenon's Attack on the Gangs】

2020-04-21 11:00:20


可能更好的阅读体验

首先要求的东西实际上等于 $$ \sum_{i=1}^n\sum_{1\leq u<v\leq n}[\operatorname{mex}(u\to v)\geq i] $$ 后面的东西的意思就是路径上恰好包含 $0\cdots i-1$ 这些数的路径数。

不难发现一个性质,即最优方案中 $0\cdots i-1$ 一定构成一条路径,且成一个单谷序列。

考虑 DP。设 $dp_{i,j}$ 表示 $i\to j$ 路径上放了 $0\cdots len-1$ 这些数时答案的最大值。

记 $f_{i,j}$ 为以 $i$ 为根时 $j$ 的父节点, $sz_{i,j}$ 为以 $i$ 为根时 $j$ 的子树大小,不难得到转移 $$ dp_{i,j}=\max\left\{dp_{f_{j,i},j},dp_{i,f_{i,j}}\right\}+sz_{i,j}\times sz_{j,i} $$ 直接记搜即可。总时间复杂度 $\mathcal{O}(n^2)$ 。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=3000+10;

int n;

struct edge { int v,nxt; } e[N<<1];
int head[N];
void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int fa[N][N],sz[N][N];
void dfs(int rt,int u,int f) {
    fa[rt][u]=f,sz[rt][u]=1;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f) continue;
        dfs(rt,v,u); sz[rt][u]+=sz[rt][v];
    }
}

ll dp[N][N];
ll calc(int u,int v) {
    if (u==v) return 0;
    if (dp[u][v]) return dp[u][v];
    return dp[u][v]=max(calc(fa[v][u],v),calc(u,fa[u][v]))+sz[u][v]*sz[v][u];
}

int main() {
    n=read();
    for (int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    for (int i=1;i<=n;++i) dfs(i,i,0);
    ll ans=0;
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j)
            ans=max(ans,calc(i,j));
    printf("%lld\n",ans);
    return 0;
}