[KTSC 2025] 完美编号 / numbering

· · 题解

传送门

考虑树的情况。

首先问题可以转化成找到一条路径，把这条路径染成单调递增，其余点染成距离最近的路径上的点。

要求不同颜色点对最小，就是要求同色连通块大小平方和最大。

假如我们钦定了一个端点，则另一个端点是可以简单 dp 求出来的。

又可以发现，要找的路径的端点一定是叶子。

感受一下，是不是有点类似树的直径？那么我们大胆假设使用求树的直径的方法做这个题也是可以的。

于是我们考虑二次 dfs，先随便钦定一个端点，找到最优的另一个端点 x，再找到以 x 为端点最优的 y，则此时 (x,y) 就是我们要找的路径。

实际测试后可以发现这么做是对的。

非树的情况也是简单的。可以发现环上的颜色都相等，于是给边双缩点，转化成树上带权问题，直接套树的做法即可。

复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e6+5,inf=1e18;
int n,m,siz[N],mk[N],f[N],g[N],dfn[N],low[N],idx=1,cnt,bh[N],sz[N];
vector<int>p[N],st;
vector<pair<int,int> >e[N];
void tarjan(int x,int y=0){
    dfn[x]=low[x]=++idx;
    st.push_back(x);
    for(auto [c,bh]:e[x]){
        if(!dfn[c]){
            tarjan(c,bh);
            low[x]=min(low[x],low[c]);
        }else if(bh!=(y^1))low[x]=min(low[x],dfn[c]);
    }
    if(dfn[x]==low[x]){
        int t;cnt++;
        do{
            t=st.back();
            st.pop_back();
            bh[t]=cnt;
            sz[cnt]++;
        }while(t!=x);
    }
}
void init(int x){
    mk[x]=1;siz[x]=sz[x];
    for(auto c:p[x]){
        if(mk[c])continue;
        init(c);
        siz[x]+=siz[c];
    }
    mk[x]=0;
}
void dfs(int x){
    mk[x]=1;
    for(auto c:p[x]){
        if(mk[c])continue;
        f[c]=f[x]+(siz[x]-siz[c])*(siz[x]-siz[c]);
        dfs(c);
    }
    g[x]=f[x]+siz[x]*siz[x];
    mk[x]=0;
}
int max_diversity(signed nn, signed mm,vector<signed> U,vector<signed> V){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=nn;m=mm;
    for(int i=1;i<=m;i++){
        int x=U[i-1],y=V[i-1];
        x++;y++;
        e[x].push_back({y,++idx});
        e[y].push_back({x,++idx});
    }
    idx=0;
    tarjan(1);
    for(int i=1;i<=n;i++){
        for(auto [c,bhs]:e[i]){
            if(bh[i]!=bh[c]){
                p[bh[i]].push_back(bh[c]);
            }
        }
    }
    init(1);
    dfs(1);
    int nw=1;
    for(int i=1;i<=cnt;i++){
        if(g[i]<g[nw])nw=i;
    }
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    init(nw);
    dfs(nw);
    int res=inf;
    for(int i=1;i<=cnt;i++)res=min(res,g[i]);
    return (n*n-res)/2;
}