Link

Codeforces1338D

Description

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

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

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

$n\leq 10^5$

Solution

约定

  • 以下我们称特殊独立集为满足题目条件的独立集。
  • 独立集的大小为独立集内的点数。

正文

首先你可以发现一个性质

  • 对于一个链 $a\rightarrow b \rightarrow c$,$a$ 和 $b$ 交, $b$ 和 $c$ 交,那么 $a$ 可能包含 $c$。

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

说的具体一点就是

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

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

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

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

证明:

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

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

证毕。

大概就是以下这种情况

illustration_1

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

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

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

大概就是以下这种情况

illustration_2

于是我们就可以用类似最大独立集的树形 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; 
}

后言

  • 根据题目的性质可以得到原题类似于最大独立集的思路。
最后修改:2020 年 04 月 14 日 06 : 36 PM
如果觉得我的文章对你有用,请随意赞赏