最大独立集

对于一棵n个结点的无根树,选择尽量多的结点,使任何两个结点均不相邻
输入n-1条无向边,输出一个最大独立集

  • d(i)表示以i为根结点的最大独立集大小

$$d(i)=Max(1+\sum_{j \in gs(i)}d(j) , \sum_{j \in s(i)}d(j))$$

  • gs(i)和s(i)分别表示i的孙子和儿子集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dp(int u,int k) //k=1表示根节点已选,k=0表示未选
{
//f[u][k]=1; //f[u][k] 表示结点u的最优值是否唯一
d[u][k]+=k;
for(int i=0;i<sons[u].size();++i){
int v=sons[u][i];
if(k==1){
d[u][k]+=dp(v,0);
//if(!f[v][0]) f[u][k]=0;
}
else{
d[u][0]+=max(dp(v,0),dp(v,1));
//if(d[v][0]==d[v][1]) f[u][k]=0; //子结点传来的最优值有多个
//else if(d[v][0]>d[v][1] && !f[v][0]) f[u][k]=0; //已选子节点最优值不唯一
//else if(d[v][1]>d[v][0] && !f[v][1]) f[u][k]=0;
}
}
return d[u][k];
}
ans=max(dp(0,1),dp(0,0));
//bool unique=0;
//if(d[0][1]>d[0][0] && f[0][1]) unique=1;
//if(d[0][0]>d[0][1] && f[0][0]) unique=1; //unique=1表示答案唯一

最小支配集

对于一棵n个结点的无根树,选择尽量少的结点,使剩余结点都与取出的结点有边相连

最小覆盖集

对于一棵n个结点的无根树,选择尽量少的结点,使所有的边都与取出结点相连

  • 最大独立集+最小覆盖集=n

二分图匹配

将树的独立集等性质扩展到图上。

重心

对于一棵n个结点的无根树,选择一个结点作为根结点,使其最大子树的结点最少

  • d(i)表示以i为根的子树结点个数

$$d(i)=\sum_{j \in s(i)}d(j)+1$$
$$Ans=Min(Max(d(j)),n-d(i)))$$

  • 只需要dfs一次,遍历每个结点,将无根树转化为有根树即可

题目

CF-581F

CF-627D

从任意根结点开始按dfs序(每次可以选任意一棵子树)遍历k个结点,使得其中的最小值最大

先二分答案
然后这题的答案与父亲结点有关,所以两次dfs
第一次求每个结点的子树的结点以及满足条件的结点个数
第二次更新答案,注意每个结点最多可以连接两个不完整的子树
对于完整的子树直接加入,对于不完整的记录最大值和次大值
然后若父亲结点对于的子树若是完整的则加入答案
注意dp存的是最多加入一棵不完整的子树的答案(这样才能转移)