题解 CF1338D 【Nested Rubber Bands】

· · 题解

评分还没出，目测难度在 2800 上下？

题意

给定一棵 n 个点的树，第 i 条边连接 u_i 和 v_i。

你需要将每一个节点画成一个二维平面上闭合几何图形，满足如果 u 和 v 之间有边相连，那么这两个点对应的几何图形边界相交。（注意包含不算边界相交）

我们定义一个序列 a_1,a_2,\ldots,a_k 是好的，当且仅当对于任意的 2\le i\le k，a_{i-1} 所对应的几何图形完全包含 a_i 所对应的几何图形。

求好的序列最长可以是多少。

（题面翻译是我写的）

题解

性质1

如果两个点之间有边相连，那么这两个点对应的图形不可能互相包含。

这一点是显然的。

性质2

对于一个序列 a_1,a_2,\ldots,a_k，这个序列对于整棵子树合法（所有其它点都能画出来），当且仅当这个序列对于 a_1,\ldots,a_k 所形成的导出子树合法。

证明：

假设我们已经画出来了一个连通子树，我们需要画出来其它所有的点。

在这个连通子树内任意取一个点当根进行 bfs，如果当前点 x 还没有画出来，就画一个圆使得它只和 x 的父节点相交。由于只要求和一个图形相交，所以一定可以画出来。

继续画下去就可以得到整棵树。

性质3

对于任意一个点 u，不可能存在三棵子树 x,y,z，使得这三棵子树中除了 x,y,z 之外，还有其它点在序列中。（是不是很绕）

证明：

考虑反证法，设 x,y,z 中分别有三个点 a,b,c 在序列中：

考虑 x 和 z 这两棵子树。由于这两棵子树中没有任意一个点和 b 有边相连，所以 x 和 z 一定位于 b 的两边：

接下来考虑 u 这个点。它和 x,z 相交，但是却不和 b 相交，这是不可能的。

思路

我们考虑不违反上述三条性质的序列。可以发现，这个序列一定满足存在一条链，使得所有点要么在链上要么和链直接相连。因为对任意一个点来说，不和它直接相连的序列中的点至多位于它的两棵子树内。大家感性理解一下。

这样我们就有了一个暴力思路：枚举一条链，把这条链以及和它相邻的点拿出来，求一个最大独立集。

这个算法显然会 TLE，我们考虑用树形 DP 的思想。

对于一个点 i ，我们设 f_{i,0} 表示在 i 的子树中，i 作为链的一端且不在序列中，能够选择的点最多有多少。

再设 f_{i,1} 表示在 i 的子树中，i 作为链的一端且在序列中，能够选择的点最多有多少。

树形 DP 的经典模型：

f_{v,1}+d_u-2\to f_{u,0} f_{v,0}+d_u-2\to f_{u,0} f_{v,0}+1\to f_{u,1}

初始别忘了让 f_{u,1}=1,f_{u,0}=d_u-2（之所以 -2 是因为链头的点选到序列中一定不会更劣，因此所有没有选择的点一定位于链的中间位置，u 的周围有 d_u-2 个点）

在转移的过程中随时更新答案：

f_{u,0}+f_{v,0}\to ans f_{u,0}+f_{v,1}\to ans f_{u,1}+f_{v,0}\to ans f_{u,1}\to ans

时间复杂度 O(n)。

代码

比赛的时候 DP 状态略微有些不同，为了写这篇题解专门又改了改：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Edge
{
    int to;
    int nxt;
}e[200005];
int n,m,edgenum,head[100005],dep[100005],pa[100005],d[100005],ans;
int f[100005][2];
void add(int u,int v)
{
    e[++edgenum].to=v;
    e[edgenum].nxt=head[u];
    head[u]=edgenum;
}
void dfs(int node)
{
    dep[node]=dep[pa[node]]+1;
    f[node][0]=0,f[node][1]=1;
    for(int hd=head[node];hd;hd=e[hd].nxt)
    {
        int to=e[hd].to;
        if(to==pa[node])continue;
        pa[to]=node;
        dfs(to);
        ans=max(ans,f[node][0]+f[to][0]);
        ans=max(ans,f[node][0]+f[to][1]);
        ans=max(ans,f[node][1]+f[to][0]);
        f[node][0]=max(f[node][0],f[to][1]+d[node]-2);
        f[node][0]=max(f[node][0],f[to][0]+d[node]-2);
        f[node][1]=max(f[node][1],f[to][0]+1);
    }
    ans=max(ans,f[node][1]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
        d[u]++,d[v]++;
    }
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

赛时提交记录：76398535