题解 CF1338D 【Nested Rubber Bands】

· · 题解

\href{http://blog.chhokmah.cn/index.php/archives/94/}{\Large\texttt{My blog}}

Description

给定一棵 n 个节点的树，每一个节点都代表了一个封闭区域。

若两个节点 (a,b) 之间有边连接，那么代表 a 所代表的封闭区域和 b 所代表的封闭区域有交，如果没有边相连，那么一定没有交。

最大化某一个点集，使得其内部的每一个节点代表的封闭区域对于其他的节点代表的封闭区域是包含或者被包含的关系。

n\leq 10^5

Solution

约定

正文

首先你可以发现一个性质

这就有点像最大独立集的做法。

说的具体一点就是

以下分析结合画图有利于理解。

我们指定一个节点 u 不选择，那么显然最优的是把与其连接的子节点中最大的一个特殊独立集取出作为中心，再把其他和 u 连接的子节点所代表的圆形依次覆盖原来的节点。

为了更加彻底的表述以上的性质，我们需要证明以下结论：

对于一个节点 u，不会存在两个以上的子节点其本身和子树对 u 有贡献。

证明：

若子节点 a,b 对 u 都有贡献，那么 a 点和 b 点所代表的圆形一定存在包含关系，我们不妨设 a 所代表的区域包含了 b

那么显然 a 的子树和 b 的子树内的所有节点不存在边相连，所以两者之间不存在边相连，所以 a 子树的区域的并一定在 b 代表的区域外，那么 a 的子树对 u 就一定没有贡献。（详细可以画图验证）

证毕。

大概就是以下这种情况

红色表示的是选择的子节点的最大独立集，紫色的为根节点，白色为其余的子节点。

我们指定一个节点 u 选择，那么结论和上面相似，即选择一个与其连接的子节点中最大的一个根节点不选择的特殊独立集。但是因为 u 选择了，所以其他的子节点不能覆盖在选择的独立集上。

接下来的分析思路就和第一种情况类似，不再赘述。

大概就是以下这种情况

于是我们就可以用类似最大独立集的树形 DP 来解决这一题。

注意需要在转移的时候随时更新答案，答案的更新和上述转移相同。

时间复杂度 \Theta(n)

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n, ans;
vector<int> g[N];
int f[N][2];

void dfs(int u, int fa) {
  f[u][0] = f[u][1] = 0;
  for (auto v : g[u]) {
    if (v ^ fa) {
      dfs(v, u);
      ans = max(ans, f[u][1] + f[v][0] + 1);
      ans = max(ans, f[u][0] + (int)g[u].size() - 2 + max(f[v][0], f[v][1]));
      f[u][0] = max(f[u][0], max(f[v][1], f[v][0]));
      f[u][1] = max(f[u][1], f[v][0]);
    }
  }
  f[u][1]++;
  if (g[u].size() >= 2)
    f[u][0] += g[u].size() - 2;
  ans = max(ans, max(f[u][0], f[u][1]));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  ans = 0;
  dfs(1, 0);
  printf("%d\n", ans);
  return 0; 
}