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;
}