CF1338D Nested Rubber Bands 题解

题意：

给定一棵 $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$ 所对应的几何图形。

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

上图的答案是 $4$ ，一种构造如下图所示

输入格式：

The first line contains integer $n$ $(3 \le n \le 10^{5})$ — the number of vertices in tree.

The $i$ -th of the next $n-1$ lines contains two integers $a_{i}$ and $b_{i}$ $(1 \le a_{i} \lt b_{i} \le n)$ — it means there is an edge between $a_{i}$ and $b_{i}$ . It is guaranteed that given graph forms tree of $n$ vertices.

输出格式：

Print the answer.

首先可以发现，两个相邻的点是不可能同时存在于合法序列中的。

我们不妨假设已知答案序列为 $b_1,b_2,\cdots,b_k$

显然这 $k$ 个点互相不相邻，于是我们可以构造同心圆来描述这种情况

其中黑色的圈可以视作某棵子树的根节点，其直接链接的圈就是它的子节点

可以发现，至多有一个子节点的答案可以贡献给根节点，其他的子节点至多在此基础上给予 $1$ 的贡献。

于是这就是一个简单的树形dp了，~~是不是非常神奇~~。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int n, res, f[N][2];
vector<int> vec[N];
void dfs(int u, int fa)
{
    f[u][0] = f[u][1] = 0;
    for(auto v : vec[u]) if(v != fa)
    {
        dfs(v, u);
        up(res, f[u][1] + f[v][0] + 1);
        up(res, f[u][0] + vec[u].size() - 2 + max(f[v][0], f[v][1]));
        up(f[u][0], max(f[v][0], f[v][1]));
        up(f[u][1], f[v][0]);
    }
    ++f[u][1];
    if(vec[u].size() >= 2) { f[u][0] += vec[u].size() - 2; }
    up(res, max(f[u][0], f[u][1]));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1, u,v; i < n; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v); vec[v].push_back(u);
    }
    dfs(1, 0); cout << res << '\n';
    return 0;
}