CF2107D

HasNoName · 2025-09-23 23:54:44 · 题解

思路

考虑用一个类似于点分治的方法写。

思路是显然的，考虑到是求字典序最大，所以路径长度一定是最重要的，其次是端点坐标。

所以可以考虑树的直径。

然后每次通过树形动态规划找到最大序号的直径，然后删除，再对剩下的子树去做。

复杂度是 O(N\log N) 的。

难点在于代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=150005;
struct G
{
    int ne,to;
}e[2*N];
struct T
{
    int d,x,y;
}ans[N];
int he[N],idx,a[N],f[N],u[N],v[N],c[N],top,sz,fat[N],vis[N],g[N],mxid[N];
void add(int x,int y)//加边
{
    e[++idx].ne=he[x];
    e[idx].to=y;
    he[x]=idx;
}
void dfs(int x,int fa)//树形dp
{
    fat[x]=fa;//记录祖先
    c[++top]=x;//块内元素
    f[x]=0;//最长路径长度
    g[x]=0;//最长的以当前根为起点的路径长度
    mxid[x]=x;//能取到g[x]的另一个端点的id最大值
    int mx=0,cmx=0,id=x,cid=x;//最长的以当前根为起点的路径长度、次最长的以当前根为起点的路径长度、能取到mx的另一个端点的id最大值、能取到cmx的另一个端点的id最大值
    for(int i=he[x];i;i=e[i].ne)//先取最长路径
    {
        int y=e[i].to;
        if(a[y]||y==fa)continue;
        dfs(y,x);
        if(g[y]>mx||(g[y]==mx&&mxid[y]>mxid[id]))
        {
            mx=g[y];
            id=y;
        }
    }
    for(int i=he[x];i;i=e[i].ne)//再取次长路径
    {
        int y=e[i].to;
        if(a[y]||y==fa||y==id)continue;
        if(g[y]>cmx||(g[y]==cmx&&mxid[y]>mxid[cid]))
        {
            cmx=g[y];
            cid=y;
        }
    }
    f[x]=mx+cmx+1;
    g[x]=mx+1;
    u[x]=max(mxid[id],mxid[cid]);//具体构造方案(f[x],u[x],v[x])
    v[x]=min(mxid[id],mxid[cid]);
    mxid[x]=mxid[id];
}
int get(int x)//得到当前联通块答案
{
    top=0;
    dfs(x,0);
    int mx=0,id=x;
    for(int i=1;i<=top;i++)//保证复杂度
    {
        int y=c[i];
        if(f[y]>mx||(f[y]==mx&&(u[y]>u[id]||(u[y]==u[id]&&v[y]>v[id]))))
        {
            id=y;
            mx=f[y];
        }
    }
    return id;
}
void run(int x)//分治，处理路径
{
    x=get(x);
    for(int i=1;i<=top;i++)vis[c[i]]=0;
    ans[++sz]={f[x],u[x],v[x]};
    int s=u[x],t=v[x],lca;//计算lca
    while(s)
    {
        vis[s]=1;
        s=fat[s];
    }
    while(t)
    {
        if(vis[t])
        {
            lca=t;
            break;
        }
        t=fat[t];
    }
    s=u[x];t=v[x];a[lca]=1;//删除路径
    while(s!=lca)
    {
        a[s]=1;
        s=fat[s];
    }
    while(t!=lca)
    {
        a[t]=1;
        t=fat[t];
    }
    s=u[x];t=v[x];//分治
    int lst=0;
    while(lst!=lca)
    {
        for(int i=he[s];i;i=e[i].ne)
        {
            int y=e[i].to;
            if(a[y])continue;
            run(y);
        }
        lst=s;
        s=fat[s];
    }
    while(t!=lca)
    {
        for(int i=he[t];i;i=e[i].ne)
        {
            int y=e[i].to;
            if(a[y])continue;
            run(y);
        }
        t=fat[t];
    }
}
bool cmp(T a,T b)//对每个联通块答案排序
{
    if(a.d!=b.d)return a.d>b.d;
    if(a.x!=b.x)return a.x>b.x;
    return a.y>b.y;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            he[i]=0;
            a[i]=0;
        }
        idx=0;
        for(int i=1;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            add(x,y);
            add(y,x);
        }
        sz=0;
        run(1);
        sort(ans+1,ans+sz+1,cmp);
        for(int i=1;i<=sz;i++)cout<<ans[i].d<<' '<<ans[i].x<<' '<<ans[i].y<<' ';
        cout<<'\n';
    }
    return 0;
}