【2023.05.07 模拟赛】T3 树数树

Description

牛牛有一棵 \(n\) 个点的有根树, 根为 1 。

我们称一个长度为 \(m\) 的序列 \(a\) 是好的，当且仅当：

• \(\forall i \in(1, m], \mathrm{a}_{\mathrm{i}}\) 为 \(\mathrm{a}_{\mathrm{i}-1}\) 的祖先或 \(\mathrm{a}_{\mathrm{i}-1}\) 是 \(\mathrm{a}_{\mathrm{i}}\) 的祖先；
• \(\forall 1 \leq i<j \leq m, a_i \neq a_j\) 。

你需要帮助牛牛求出最长的序列长度。

Solution

对于节点 \(x\)，它能够将两条子树内的序列连接起来。既然这样，不妨考虑对于每个节点，构建一个堆，来记录该子树内的所有可能的序列长度。那么在合并两个儿子的时候，可以用可并堆或者启发式合并来实现。时间复杂度 \(\mathcal O(n\log n) \sim \mathcal O(n\log ^2n)\)。

Code

#include<queue>
#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
int T,n,tot,id[N];
struct node {int to,next,head;}a[N<<1];
priority_queue<int> q[N];
void add(int x,int y)
{
    a[++tot].to=y;a[tot].next=a[x].head;a[x].head=tot;
    a[++tot].to=x;a[tot].next=a[y].head;a[y].head=tot;
}
void merge(int &x,int &y)
{
    if (q[x].size()<q[y].size()) swap(x,y);
    while (!q[y].empty()) q[x].push(q[y].top()),q[y].pop();
}
void dfs(int x,int fa)
{
    for (int i=a[x].head;i;i=a[i].next)
    {
        int y=a[i].to;
        if (y==fa) continue;
        dfs(y,x);
        merge(id[x],id[y]);
    }
    x=id[x];
    if (q[x].empty()) q[x].push(1);
    else
    {
        if (q[x].size()==1)
        {
            int v=q[x].top();q[x].pop();
            q[x].push(v+1);
        }
        else
        {
            int v1=q[x].top();q[x].pop();
            int v2=q[x].top();q[x].pop();
            q[x].push(v1+v2+1);
        }
    }
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        for (int i=1;i<=n;++i)
            id[i]=i;
        for (int i=1;i<n;++i)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        dfs(1,0);
        printf("%d\n",q[id[1]].top());
        tot=0;
        for (int i=1;i<=n;++i)
            a[i].head=0;
        while (!q[id[1]].empty()) q[id[1]].pop();
    }
    return 0;
}