题解 CF1528C Trees of Tranquillity

· · 题解

在实现难度上，个人更倾向于本题使用欧拉序列+ set 去实现。本题解主要是对官方代码进行一个分析。

考虑欧拉序列的性质。详细性质可以参见本文：树的其他知识——欧拉序列。其中一个很重要的性质，就是任意两个节点对应的区间 [st_1,ed_1],[st_2,ed_2]，这俩区间要么完全包含要么完全不相交。并且，如果是包含关系的话，一定有祖先关系。因而我们利用好这个性质。

考虑最后最大团的组成。它需要这里面每个节点都和其他的都有边相连，由于有第一个条件——Soroush 树上有祖先关系的存在，这些点必然是 Soroush 上的一条链。 为了构造最大团，最好使得初始待选择的点尽可能的多，因而是 Soroush 树上的一条链。

接下来考虑这条链上满足第二条件的点集。由于欧拉序列的性质，我们将问题等价于从这些点中选取一些，使得它们都不相交（等价于不存在包含关系）。那么一个贪心的基本原则：能选小区间就不选大区间，因而有官方题解的两条原则：

  1. 如果之前的链上无区间覆盖当前节点区间，直接贪心加入；

  2. 如果有，保留小区间，删去大区间。

接下来就是实现问题。

首先是求 Keshi 树的欧拉序列。然后去遍历 Soroush 树，在 set 中仅维护当前节点到根节点这些区间中合法的部分，然后统计答案。我们就不一定要求一定要到根节点去了。

鉴于 CF 的官方题解实现的较为简洁，因而在这里我对 CF 的题解代码进行一个详细的评述。

下面是一个大体的流程：

这里是判断一个点所对应的欧拉序列区间是否在 set 中有重叠部分，以及重叠情况，来判断是否要加点。

int judge(int place)
{
    auto iter = exist.lower_bound(make_pair(st[place], place));
    //首先是找到该点附近的几个区间。注意这里我们在set中维护的是它的起始点和当前节点编号。可以存储当前节点对应的欧拉区间（即开始和结束），但是这里不便于后面的处理。
    //这里使用起始点和当前节点编号的另一个好处在于，在set中排序时是优先按照起始点在排序，因而可以快速找到这样的区间。
    //iter现在指向的是第一个大于当前点对应区间的区间。由于欧拉序列的性质，两个点对应的欧拉序列起始点和终止点必不相同。
    //因而现在的情况是 iter对应的点的起始点start>st[place]
    if(iter!=exist.end() && ed[iter->second]<=ed[place])
    //如果当前点的终止点还在place终止点前，那么证明这是个被place包络的一个小区间，place就不必加入set了。
        return -2;
    //特供于set为空。
    if(iter==exist.begin())
        return -1;
    iter--;
    //返回-1的含义：当前set中无包络区间。
    //返回-2的含义：set中已有较小区间，当前点不必加入
    if(ed[iter->second]<ed[place])
    //现在的起始点一定在st[place]前，那么如果当前终点也在place前，证明无包络。
        return -1;
    exist.erase(iter);
    //iter指向的区间为大区间，但是这个老区间辈分高，因而在place子树处理完后要补回来，因而需要记录。但是在place子树下，这个大区间是没有必要的，因而要删掉。
    return iter->second;
}

考虑 judge 函数的定义，我们有如下的主要递归函数：

void solve(int place)
{
    int res = judge(place);
    if(res!=-2)
    //只要不是-2的不必加入，在处理place子树的时候都需要加入。
        exist.insert(make_pair(st[place], place));
    ans = max(ans, (int)exist.size());
    for (int i = headers[0][place]; i; i = que[0][i].next)
        solve(que[0][i].to);
    if(res!=-2)//回溯工作
    {
        exist.erase(make_pair(st[place], place));
        //首当其冲，子树遍历完它也不在正在求的链上了，删掉
        if (res != -1)//有老的、包络大区间，因而需要恢复
            exist.insert(make_pair(st[res], res));
    }
}

其余代码实现就非常简单了。