树形 DP 中的换根 DP 问题又被称为二次扫描,通常不会指定根结点,并且根结点的变化会对一些值,例如子结点深度和、点权和等产生影响。
通常需要两次 DFS,第一次 DFS 预处理诸如深度,点权和之类的信息,在第二次 DFS 开始运行换根动态规划。
我在此就通俗易懂的说说个人理解,理解不到位之处还望指出。
所谓换根DP,就是基于原有的状态,通过相邻节点进行转换后,现有的状态仅仅只需要进行微小的变动即可达到完美相邻状态间的切换。
而对应在这题,要计算不同根下的树高,首先需要计算出原始状态,这里用 0 0 0 号节点为根来计算。那么之后进行换根操作,理应从 0 0 0 号节点开始。
我们定义:
那么如果当前 u u u 为根节点,现在要进行换根操作到 j j j 节点为根。明确 j j j 是 u u u 的其中一个相邻节点,所以 j j j 换为根后, u u u 的子树高状态应当扣除掉之前维护中包含的 j j j 子树高的状态。而怎么样才会影响到 u u u 的状态的改变呢?无非是两种情况: j j j 树高是 u u u 树高的最大值,除去后, u u u 树高应变为次大值 + 1 +1 +1;反之, u u u 树高仍是相邻节点的最大值树高 + 1 +1 +1。
那么考虑完了两个根节点之间状态的转变,根相邻节点的状态应该如何变化?在这仅以 u u u 节点的相邻节点考虑,对称状态为 j j j 的相邻节点。由于我们维护的状态是在 h h h 数组中, h [ i ] h[i] h[i] 仅表示当前某个节点为根下, i i i 的子树高。所以当根由 u u u 向 j j j 转变后,实际上对 u u u 的除 j j j 的相邻节点,这些点的树高状态并不会改变,读者可以自己思考。
上述就实现完成了换根后当前 h h h 数组维护的状态的转变,如下代码所示:
for (auto j: e[u]) {
if (h[j] == mx1) h[u] = mx2 + 1; // j点是最大的树高,u的树高是次高+1
else h[u] = mx1 + 1; // j点不是最大树高,u的树高是最高+1
dfs2(dfs2, j);
}
如何更新最后想要求得的 f f f 数组呢?
f [ i ] f[i] f[i]:表示 i i i 为根下, i i i 的子树高。
那么在 d f s 2 dfs2 dfs2 ,第二次DFS中,执行换根 u − j u-j u−j 前,当前根 u u u 的 f [ u ] f[u] f[u] 直接更新即可:
f[u] = mx1 + 1;
此题全部代码如下:
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
vector<int> e[n + 1]; // 构建图的邻接表
for (auto edge: edges) {
int x = edge[0], y = edge[1];
e[x].push_back(y);
e[y].push_back(x);
} // 建图
int h[n + 1]; memset(h, 0, sizeof h); // 0为根下的原树高
auto dfs1 = [&](auto &&dfs1, int u, int f) -> int {
int s = 0;
for (auto j: e[u]) {
if (j != f) s = max(s, dfs1(dfs1, j, u));
}
h[u] = s + 1;
return h[u];
};
dfs1(dfs1, 0, 0); // dfs1跑出h数组
int f[n + 1]; memset(f, 0, sizeof f); // 维护以i为根的树高f[i]
auto dfs2 = [&](auto &&dfs2, int u) -> void {
int mx1 = 0, mx2 = 0; // 最大、次大
for (auto j: e[u]) {
// 跑出u的邻接点的mx1,mx2
if (mx1 < h[j]) mx2 = mx1, mx1 = h[j];
else if (mx2 < h[j]) mx2 = h[j];
}
f[u] = mx1 + 1; // 当前u为根的树高 = 最大子树高+1
for (auto j: e[u]) {
// 换根操作!-> 维护h数组的变动
if (f[j] != 0) continue; // 已经算过就不在计算了
if (h[j] == mx1) h[u] = mx2 + 1; // j点是最大的树高,u的树高是次高+1
else h[u] = mx1 + 1; // j点不是最大树高,u的树高是最高+1
dfs2(dfs2, j);
}
};
dfs2(dfs2, 0); // 跑出f数组
int mx = n;
vector<int> res;
for (int i = 0; i < n; i++) {
if (mx > f[i]) mx = f[i], res.clear();
if (mx == f[i]) res.push_back(i);
}
return res;
}
};
class Solution {
public:
long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
vector<int> e[n + 1];
for (auto edge: edges) {
int x = edge[0], y = edge[1];
e[x].push_back(y);
e[y].push_back(x);
}
long long hx[n + 1], hn[n + 1]; memset(hx, 0, sizeof hx); memset(hn, 0, sizeof hn);
auto dfs1 = [&](auto &&dfs1, int u, int f) -> void {
long long mx = 0, mn = 0;
for (auto j: e[u]) {
if (j == f) continue;
dfs1(dfs1, j, u);
mx = max(mx, hx[j]);
mn = min(mn, hn[j]);
}
hx[u] = mx + price[u];
hn[u] = mn + price[u];
};
dfs1(dfs1, 0, -1);
long long fx[n + 1], fn[n + 1]; memset(fx, 0, sizeof fx); memset(fn, 0, sizeof fn);
auto dfs2 = [&](auto &&dfs2, int u) -> void {
long long mx1 = 0, mx2 = 0;
long long mn1 = 0, mn2 = 0;
for (auto j: e[u]) {
if (mx1 < hx[j]) mx2 = mx1, mx1 = hx[j];
else if (mx2 < hx[j]) mx2 = hx[j];
if (mn1 > hn[j]) mn2 = mn1, mn1 = hn[j];
else if (mn2 > hn[j]) mn2 = hn[j];
}
fx[u] = mx1 + price[u];
fn[u] = mn1 + price[u];
for (auto j: e[u]) {
if (fx[j] != 0 && fn[j] != 0) continue;
hx[u] = hx[j] == mx1 ? mx2 : mx1; hx[u] += price[u];
hn[u] = hn[j] == mn1 ? mn2 : mn1; hn[u] += price[u];
dfs2(dfs2, j);
}
};
dfs2(dfs2, 0);
long long res = 0;
for (int i = 0; i < n; i++) res = max(res, fx[i] - /*fn[i]*/ price[i]);
return res;
}
};
class Solution {
public:
int rootCount(vector<vector<int>>& edges, vector<vector<int>>& guesses, int k) {
int n = edges.size();
vector<int> e[n + 1];
for (auto &edge: edges) {
e[edge[0]].push_back(edge[1]);
e[edge[1]].push_back(edge[0]);
}
map<pair<int, int>, int> mp;
for (auto &x: guesses) {
mp[{
x[0], x[1]}] = 1;
}
int res = 0;
function<void(int, int)> dfs1 = [&](int u, int f) -> void {
for (auto &j: e[u]) {
if (j == f) continue;
if (mp.count({
u, j})) res++;
dfs1(j, u);
}
};
dfs1(0, -1);
int ans = 0;
function<void(int, int)> dfs2 = [&](int u, int f) -> void {
if (res >= k) ans++;
for (auto &j: e[u]) {
if (j == f) continue;
int tmp = 0;
if (mp.count({
u, j})) tmp--;
if (mp.count({
j, u})) tmp++;
res += tmp;
dfs2(j, u);
res -= tmp;
}
};
dfs2(0, -1);
return ans;
}
};
文章浏览阅读242次。虚假评论不仅误导了消费者的购买决策,损害了商家的信誉,还可能导致市场竞争的扭曲和不公平。此外,随着电子商务和社交媒体的快速发展,虚假评论的传播范围和影响力也越来越大。例如,某些网红或明星为了增加自己的粉丝数量和关注度,会雇佣“水军”发布虚假评论来提高自己的口碑;基于上述背景,本论文旨在研究基于数据挖掘的虚假评论识别方法,通过挖掘和分析文本、情感极性等信息,实现对虚假评论的有效识别。数据处理时,应该以utf-8编码,不然读出来的数据较乱,修改数据形式,读取Excel文件,以utf-8编码。_虚假评论识别系统
文章浏览阅读49次。这几周朋友几篇文章介绍了改红色修改的文章. 关联文章的地址一般在将别人的Android程序导入到自己的环境当中时会出现各种各样的问题,致使程序上出现错误而不能运行。一般的处理步调如下:步调一 对于显而易见的错误,如上图,可以直接定位到错误文件的位置,直接纠正就行了。步调二...
文章浏览阅读583次,点赞11次,收藏9次。回归预测 | Matlab基于SO-BiLSTM蛇群算法优化双向长短期记忆神经网络的数据多输入单输出回归预测_sobi算法matlab实现
文章浏览阅读469次。student.c文件如图所示#include<stdio.h>#include<stdlib.h>#include<time.h>#include<string.h>#include"student.h"INT32 main(VOID){CHAR chstuName[MAXNAMELENGTH];NODE psthead = cr..._用c语言的双向链表实现学生管理系统
文章浏览阅读3.1k次。我们整合boot项目的时候都是引入 xxx-start 依赖,但是现在大多数的整合RocketMQ都还不是这样。我花了一天时间使用rocketmq-spring-boot-starter整合,使得操作起来更加简单。1、说明1-1:rocketmq-spring-boot-starter 提供了一个 rocketMQTemplate 使得发消息更加简单,它底层也还是基于DefaultMQP..._rocketmq-spring-boot-starter
文章浏览阅读387次。scala数组、元组、集合、类型转换、循环退出_scala中循环元组
文章浏览阅读379次,点赞4次,收藏5次。所有现代浏览器都内置了屏蔽弹窗的程序,因此大多数意料之外的弹窗都会被屏蔽。在浏览器屏蔽 弹窗时,可能会发生一些事。如果浏览器内置的弹窗屏蔽程序阻止了弹窗,那么 window.open()很可 能会返回 null。在浏览器扩展或其他程序屏蔽弹窗时,window.open()通常会抛出错误。
文章浏览阅读364次。1.注册功能:个人基本信息以及目标院校(正在考研的)和就读学校(已经上岸的)方便区分是否考研成功,这个地方可以给一个下拉选项是备研和研究生,选择备研就是输入目标院校,研究生就是填写自己就读的院校(但是需要发送验证照片—身份证和学生证或录取通知书给管理员)。论文首先阐述了考研资料分享系统的开发,并对该系统进行了较详细的需求分析,探讨了考研资料分享系统的功能需求、业务流程、系统结构和数据库设计等方面的问题。(3)还有一个游客的角色,可以浏览,但是不能进行其他的操作,进行其他的操作要给出提示需要登录或注册账户。_visualstudiocode可行性分析
文章浏览阅读845次。????文章目录一、????????网站题目二、️网站描述三、????网站介绍四、????网站演示五、️ 网站代码????HTML结构代码????CSS样式代码六、???? 如何让学习不再盲目七、????更多干货一、????????网站题目????汽车网站、????汽车介绍、????汽车官网、汽车租赁、企业网页 、等网站的设计..._网页设计与制作html+css+javascripe电子版
文章浏览阅读789次,点赞18次,收藏27次。群晖是一种NAS(网络附属存储)系统,在生活中主要扮演个人私有云角色,可以将文件存储于 NAS,并通过网页浏览器或手机应用程序可实现存储和共享,同时还提供的丰富应用以方便管理应用。借助群晖提供的 QuickConnect 快连服务,无需随身携带存储设备,即可以随时随地访问NAS。因为这些优点,群晖往往被当做是NAS的首选。但偏偏这次被上勒索病毒了,通过资料查询发现该病毒早在2019年安全专家就已经分析过并已提供预警信息,一旦感染,其中的文件都会被加密,并通过留下的文件索要比特币。
文章浏览阅读2.2k次,点赞2次,收藏15次。2 Menu Bar在菜单中栏中,可以添加多个菜单,但是菜单并不负责执行具体的操作,而是在菜单中添加不同的 “动作”(QAction)来完成。在菜单栏中除了添加菜单,还可以直接添加 QAction。2.1 简单示例..._qmainwindow
文章浏览阅读2.5k次。 1.花朝月夕,如诗如画。祝你生日快乐、温馨、幸福…… 2.但愿真正的快乐拥抱着你,在这属于你的特别的一天,祝你生日快乐! 3.日月轮转永不断,情若真挚长相伴,不论你身在天涯海角,我将永远记住这一天。祝你生辰快乐! 4.让我为你祝福,让我为你欢笑,因为在你生日的今天,我的内心也跟你一样的欢腾、喜悦。祝你快乐!40.难忘是你我纯洁的友情!可贵是永远不变的真情!高兴是能认识你!献上我最_生日祝福短信测试用例