栗题
给你一棵大小为 \(n\) 的树，求这棵树的最大独立集是多少。
最大独立集指的是一个最大的点集使得其中的点两两没有边相连
\(N\leq10^5\)
solution
没有上司的舞会？？
也就是如果儿子节点选了，其父亲节点就不可以选；
枚举每个点选不选就好了，根据树上dp模型，从下往上转移就好了
状态
\(dp[i][0/1]\) 表示做完了 i 的子树，i 点是否选的最大独立集
转移
如果父亲节点不选孩子节点就可以任意选择
如果父亲节点选了的话，孩子节点就不能选了
node
void Dp{int u,int p){
dp[u][0] = 1;
dp[u][1] = 0;
for (int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == p)continue;
Dp(v, u);
dp[u][0] += dp[u][1];
dp[u][1] += max(dp[v][0],dp[v][1]);
}
}
树的直径
给你一颗点数为 \(n\) 的树，让你求这棵树的直径是多少（求最长的两个点之间的距离）
\(N\leq100000\)
solution
先随便找个点，跑一遍dfs找出最远的点，然后从这个最远的点再跑一遍dfs，跑到的最远的点就是树的直径（离每一个点最远的点肯定是直径的其中一个端点）
具体证明：树的直径证明方法
f[i]表示以 i 为根节点到子树的叶子节点最远距离
g[i]表示以 i 为根节点到子树的叶子节点次远距离
对于一个节点，它到叶子节点的最远距离和次远距离必定不一个样，最后只需要把根节点的最大值和次大值相加就是直径
转移：
如果当前遍历的边大于最大值，就把最大值替换，次大值改为原来最大值，否则只更新次大值
void Dp(int x,int fa){
for (int i = head[x]; i; i = e[i].nxt){
int v = e[i].v;
if(v == fa)continue;
dp(v, x);
if (f[x] < f[v] + e[i].w){
g[x] = f[x];
f[x] = f[v] + e[i].w;
}
else if(g[x] < f[v] + e[i].w)
g[x] = f[v] + e[i].w;
ans = max(ans,f[x] + g[x]);
}
}
简单变式
- 一棵无向树，结点为n \(\leq 10,000\)，删除哪些结点可以使得新图中每一棵树结点数小于等于 \(n/2\) 也就是求重心
- 树的覆盖集，求最少选几个点能覆盖所有边，也就是不存在一条边两边点都没被选（本质？）和最大点独立集互补
- 最大权独立集？
几道栗题
给定一棵有 \(n\) 个点的树，以及 \(m\) 条树链，其中第 \(i\) 条树链的价值为 \(w_i\)，请 选择一些没有公共点的树链，使得价值和最大
\(n,m\leq 1000\)
solution
当然是树形dp，设f(x)表示以x为根的子树内选取不相交的树链的价值和的最大值。枚举一条LCA为 x 的链（u, v, w)，那么当前的价值就为w+除去u, v 路径上所有的点后，深度最小的点 f 的和
复杂度
\(O（M*N）\)
树链剖分优化：\(O(M*log(n)^2)\) 写一次挂一次
给出了一棵二叉树，点数为 \(n\)，然后要求每个点和其左儿子和其右儿子三者两两之间颜色（红、绿、蓝）互不相同，求最多能有多少点被染成绿色
\(N\leq 10^5\)
solution
咋还是上司的舞会
\(f[i][0] ，f[i][1]，f[i][2]\) 分别表示根是绿红蓝三种颜色时的最多/最少绿色的数量，按照约束转移就好了
给出一棵树，每个点上都有 \(W_i\) 的矿石，现在可以在一些点上设立仓库，每设立一个仓库，就要花费 \(K\) 的代价。最后每个点的代价如下计算，如果离他最近的点的距离为 \(dis\)，则代价为\(??_?? × ??(??????)\) 最小化总代价。树边长度都为 1
\(N\leq 200\)
solution
状态
\(f[i][j]\) 表示 i 的子树内所有点都确定了往哪送，并且 i 送到 j 号点，并且 j 号点现在还未建立仓库（j号点的 K还没有算入dp值）的最小代价
转移
首先 \(f[i][j]\) 要加上从 i 到 j 的代价，然后考虑 i 的每一个儿子首先\(f[i][j]\) 要加上从 i 到 j 的代价，然后考虑 i 的每一个儿子 x
如果 x 也运往 j 那这个子树的代价就是 \(f[x][j]\)
如果 x 不运往 j 那它绝对不可能运往 i 上面的其他点（那还不如 j 呢）
那就肯定运往 i 子树的其他一个点
给出一棵 \(n\) 个点的有根树，每个节点都是一个物品，具有价值 \(V_i\)，如果一 个物品要被选择，那么它的父亲必须被选择
求选择至多 \(m\) 个物品的最大价值和
\(n \leq 1000\)
solution
状态
\(f[i][j]\) 表示再以 i 为根的子树中选择，i 强制被选，选择 j 个点的最大价值
转移
经典树形dp，把孩子暴力合并在父亲上，合并就枚举孩子选了多少个点就好了
一般分析时间复杂度方式，状态数 \(N^2\) 转移的时候为 \(N\) ，总的复杂度 \(N^3\)
实际上我们考虑每次合并的时候相当于是一组点对数量的复杂度，总的来看的话就是 \(n\) 个点点对的数量，均摊复杂度 \(O(N^2)\)
给出一棵 \(n\) 个点的有根树，每个节点都是一个物品，具有价值 \(V_i\) 和重量\(W_i\)， 如果一个物品要被选择，那么它的父亲必须被选择。
求限制重量 \(m\) 内的最大价值和\(n\leq 1000,m\leq 1000\)
solution
这个题较上一个题，不在是点的数目，而是重量，所以这里就要枚举重量了
状态
\(f[i][j]\) 表示再以 i 为根子树中选择， i 强制被选，重量为 j 的最大价值；
转移
枚举孩子选了多少重量，将一个孩子合并到父亲上就阔以了
发现和上题一个样，就是把枚举的 k 成了每个孩子的重量而不是数目
两个一维数组的背包合并是 \(n^2\) 的
但一个一维数组和一个单独的物品合并是线性的
another solution
如果不选一个点，就跳过代表他的dfs上连续的一段，
状态
设 \(f[i][j]\) 表示 dfs 序上第 i 个点到第 n 个点，选了 j 的重量得到的最大的价值是 多少。i 可以选也可以不选。不选的话就要跳过整个子树(子树对答案没有贡献，就不用求了)，T[i] 表示 dfs 序为 i 的点标号
转移
不是每次将孩子与自己合并，我们直接把 dp 数组复制再传给孩子，再从 孩子递归下去，最后原来自己的 Dp 数组和孩子的 Dp 数组直接在对应重量 的价值中取 max
实现方法
对于节点 u，对 u 节点的 dp 数组中加入 u 点的物品
Dpson数组 = dp数组
递归计算son中的dp值，传参数的是dpson数组
最后回溯到u就好了
对每个 i 都做一个dp[i] = max {dpson[i],dp[i] }
上面做的树行dp都是从下往上推，而这些是从上往下推得到信息，再向上推
栗题
一棵边带权值 \(n\) 个点的树，求每个点在树上的最远距离
\(N\leq10^5\)
solution
很明显，距离每个点的最远点一定是直径两端的其中一个
跑两边dfs（dp也可以），求出树的直径的两个端点，然后分别求出两个端点到其他所有点的距离，最后就能求出每个点的最远距离
对于每个点，其最远距离又可能是它到子树中的最长距离，又可能是次长，还又可能是向上的最长最长距离（对于每个点都只能这样延伸）
状态：
\(dp[u][0]\) ：是向下最长的
\(dp[u][1]\) : 是向下次长的
\(dp[u][2]\) : 是向上最长的
答案就是三者的的最大值
求子树中最长和次长上面和上面相同
求 v 向上的最长值？？
两种情况
如果 v 的父亲 u 不是根，那就继续用 u 向上的最大值加上 e[i].w 来更新；
如果 u 是树根，就又有了两种情况，一种是 u 点向下的最长路径经过 v,那就只好用次大值来更新；否则直接用最大值更新就好了
void dfs(int u){
for (int i = head[u]; i;i = e[i].nxt){
int v = e[i].v;
dp[v][2] = max(dp[u][2], dp[v][0] + e[i].w == dp[u][0]? dp[u][1]:dp[u][0]) + e[i].w;
dfs(v);
}
}
发现这个问题不像之前，只处理子树就能统计所有答案，还需要知道父亲那边的信息；
因此我们要进行两次dfs
1：一遍求出每个点子树内的信息。
2：另一遍从根往下遍历的时候计算维护出每个点父亲枝的信息
换根dp
如果像前面的题目，以一号点为根，然后得到了以一号点为根的所有信息，但我们要求全局答案，所以我们枚举每个根都算一遍，但但复杂度很高；
如果我们已经知道 1 号点作为根的所有信息，通过一些加加减减，就可以得到以 1 号点的孩子所有用的信息，现在把 1 号点看作根，就完成了换根操作，dfs实现
理解
从下到上的dp，根的答案就已经求好了， 而其他的点只有孩子枝的信息，缺少父亲枝的信息。 （因为所有从原始根出去的分支的信息都计算完了，但是其他的点的父 那一枝的信息是没有通过从下而上的 dp 计算出来的，我们第二遍 dfs 就 是求每一个点父亲枝的信息）
我们肯定是不能对每一个点作为根跑一遍 \(O(n)\) 的 dp
所以我们第二遍 dfs 过程中就求出了每个点父亲枝的信息，这样该点所需计算答案的所需信息都有了。对应的算答案就好。
基环树，又叫环套树，就是树上加上一条边
如果把哪个环视为中心，可看成：有一个环，环上的每个点都有一棵子树的形式
基环树要对两部分处理：树处理和环处理
基环树问题处理方法
dfs找环
多这个基环树 dfs 遍历，对于一个在图， 它 dfs 树上的每一个返祖边 (v→u)， 和 dfs 树上构成的路径就会构成一个环。找到这个返祖边即可，tarjan就挺香
void dfs(int u, int f){
fa[u] = f;
vis[u] = true;
for (int i = head[u]; i; i =e[i].nxt){
int v = e[i].v;
if (v == f){
continue;
f = -1;
}
if(!vis[v]) dfs(v, u);
else {
int tmp = u; circle[cnt=1] = u;
do{
tmp = fa[tmp]；
circle[++cnt] = tmp;
}while(v != tmp);
found = true;return;
}
if(found) return;
}
}
注意： n 个点 n 条边不一定是个基环树，准确来讲是基环树森林，所以就要枚举每一个点
for (int i = 1; i <= n; i++)
if(!vis[u])dfs(i, 0);
删边
如果断开一条边，就可以当作一棵树来处理，所以就不用找出整个环来，只需要找出一个在环上的边就好了
void circle(int u, int f){
vis[u] = true;
for (int i = head[u]; i;i = e[i].nxt){
int v = e[i].v;
if(f == v){f = -1;continue};
if(vis[v]){if(!rt1)rt1 = u,rt2 = v;continue;}
circle(v, u);
}
}
基环内向树
一个有向图，构成类似基环树的结构，每个点都有且仅有一个出度，
并且环外的节点方向指向环内
图中每个点都有一个唯一的出度，则本质是一个基环内向树森林，而不是基环树
任何一个点沿着唯一出边都会走在环上，可以随便选一个点通过循环就可以找到基环树的环
基环外向树
和基环内向树相反，它有且只有一个入度，并且由环指向环外
栗题
\(N\) 个人，每个人都有一个战斗力和一个讨厌的人（不是他本身），要求一 个总战斗力最大的人的集合，满足集合内部两两不互相讨厌
\(N \leq 10^5\)
solution
把这个讨厌关系的图画出来就是一个基环内向树，然后求最大权独立集
求最大独立内向和外向和无向图没有区别，就是相邻的不能选
这里基环树上有且仅有一个环，所以就从环上任意一条边（u，v）断开环
分两种情况：①选 u，不选 v ②选 v, 不选 u ③都不选；取最大值
破环成链就成了上面的树形 dp
找环的时候用 dfs，或者一个点顺着父亲一直走直到走到一个曾经走过的点就找到了一个环
node 最大权独立集
void dfs(int u, int fat){
f[u][0] = 0;f[u][1] = val[u];
for (int i = head[u]; i; i = e[i].nxt){
int v = e[i].v;
if(v == rt) continue;
if(fat == v){
fat = -1;continue;
}
dfs(v, u);
f[u][0] += max(f[v][0], f[v][1]);
f[u][1] += f[v][0]
}
}
枚举断开哪个边，哪个边强制不选，取最优
int work(){
int ans = 0;
for (int i = 1; i <= n; i++)
if (!vis[i]){
rt1 = rt2 = 0;
circle(i, 0);//枚举断开边的两个端点rt1,rt2
int k = 0;
rt = rt1;
dfs(rt1, rt2);
k = f[rt1][0];
rt = rt2;
dfs(rt2, rt1);
k = max(k, f[rt2][0]);
ans += k;
}
}
栗题
求基环森林中的每棵基环树的直径之和
点数 \(n\leq10^6\)
solution
先找环，然后有两种情况
1：在以一个环上的节点为根的外向树直径
2：以环上两个节点分别为根的最大深度在加上两个节点在环上的距离（这两个环上的点分别各向外延申了一棵树）
第一种情况就是树形dp
第二种情况要处理出以环上每个节点为根的最大深度 \(d[i]\)，环上的点重标号，选环上的1号点为基准点，求出 \(s[i]\) 表示 i 号点到 1 号点的距离，sum 为总的环长，设我们找的两个环上节点是 i，j
优化
把式子中的 min 去掉
考虑枚举所选的两个点的最后一个 i，然后求对于i，离 i，最远的 j,的距离是多少，然后对于每个 i 的答案求最大值就是整个基环树的直径
第一种情况：\(s[j]\geq s[i] - sum/2\) ，求 d[j] - s[j] 的最大值即可，注意可选的 j 的区间会移动，所以用单调队列优化
第二种情况：\(s[j] < s[i] - sum/2\) ，这个区间只会变大，所以直接记录s[j] + d[j] 最大值即可
原文：https://www.cnblogs.com/Arielzz/p/14408855.html