当前位置:网站首页>Infected Tree(树形dp)
Infected Tree(树形dp)
2022-07-05 08:22:00 【山中一扶苏】
原题链接
题目描述
Misha发现了一棵二叉树,它的顶点编号从到。二叉树是一种包含顶点和边的无环连通双向图。每个顶点最多有一个度,而根顶点是有个数的顶点,它最多有一个度。
不幸的是,树根被感染了。
以下过程发生的次数:
Misha要么选择一个未被感染(也没有被删除)的顶点,并删除它,所有的边都有一个端点在这个顶点,或者什么都不做。
然后,感染扩散到由一条边连接到已感染顶点的每个顶点(所有已感染顶点仍然是感染的)。
由于Misha没有太多时间思考,请告诉他他可以从感染中拯救的最大顶点数是多少(注意删除的顶点不计入保存)
输入样例
4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15
输出样例
0
2
2
10
算法
(树形dp)
本题可以通过维护一个 dp 数组可以快速统计 每一个点作为根节点保留左子树或者保留右子树的最大保留人数 ,从而最后通过 dfs 过程中更新迭代,生成最后需要的答案。
值得注意的是题目的删除点及其子树的顺序是从根到枝叶,但在树形 dp 的统计过程中应该从枝叶到根进行 dp 数组统计,因为最后保留的都是每一层的枝叶,一般的树形 dp 业主要是以这样的方式统计
状态方程:
dp[u][0] = sum[l[u]] - 1 + max(dp[r[u]][1],dp[r[u]][0]);//保留左子树
dp[u][1] = sum[r[u]] - 1 + max(dp[l[u]][1],dp[l[u]][0]);//保留右子树
C++ 代码
时间复杂度 O ( n ) O(n) O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
vector<int> g[N];
int dp[N][2];//每一个点作为根节点保留左子树或者保留右子树的最大保留人数
int sum[N],l[N],r[N];//以u为根节点能够保留的总人数,u节点的左节点与右节点
void pre_dfs(int u,int fa)//预处理
{
sum[u] = 1;
for (int i = 0;i < g[u].size();i ++ ) {
int j = g[u][i];
if (j == fa) continue;
//经典代码,利用dfs的规律分别指定左右节点
if (l[u] == 0) l[u] = j;
else r[u] = j;
pre_dfs(j,u);
sum[u] += sum[j];
}
}
void dfs(int u,int fa)
{
dp[u][1] = dp[u][0] = 0;//初始化
for(int i = 0;i < g[u].size();i ++ ){
int j = g[u][i];
if (j == fa) continue;
dfs(j,u);
//最后进行dp统计
dp[u][0] = sum[l[u]] - 1 + max(dp[r[u]][1],dp[r[u]][0]);//save left subtree
dp[u][1] = sum[r[u]] - 1 + max(dp[l[u]][1],dp[l[u]][0]);//save right subtree
}
}
int main()
{
int t;
cin >> t;
while (t -- ) {
int n;
cin >> n;
int m = n - 1;
for (int i = 1;i <= n;i ++ ) {
sum[i] = l[i] = r[i] = 0;
g[i].clear();
}
for (int i = 0;i < m;i ++ ) {
int u,v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
pre_dfs(1,1);
dfs(1,1);
cout << max(dp[1][0],dp[1][1]) << '\n';
}
return 0;
}
边栏推荐
- Arduino uses nrf24l01+ communication
- [cloud native | learn kubernetes from scratch] III. kubernetes cluster management tool kubectl
- On boost circuit
- Shell script
- Installation and use of libjpeg and ligpng
- Halcon's practice based on shape template matching [2]
- [tutorial 19 of trio basic from introduction to proficiency] detailed introduction of trio as a slave station connecting to the third-party bus (anybus PROFIBUS DP...)
- Sizeof (function name) =?
- Imx6ull bare metal development learning 2- use C language to light LED indicator
- Keil use details -- magic wand
猜你喜欢
Summary -st2.0 Hall angle estimation
Simple design description of MIC circuit of ECM mobile phone
Introduction of air gap, etc
[tutorial 19 of trio basic from introduction to proficiency] detailed introduction of trio as a slave station connecting to the third-party bus (anybus PROFIBUS DP...)
Relationship between line voltage and phase voltage, line current and phase current
PMSM dead time compensation
Halcon's practice based on shape template matching [1]
Class of color image processing based on Halcon learning_ ndim_ norm. hdev
Various types of questions judged by prime numbers within 100 (C language)
Briefly talk about the identification protocol of mobile port -bc1.2
随机推荐
STM32 --- configuration of external interrupt
STM32 single chip microcomputer - external interrupt
QEMU demo makefile analysis
Halcon's practice based on shape template matching [1]
Sql Server的存储过程详解
Adaptive filter
Simple design description of MIC circuit of ECM mobile phone
Management and use of DokuWiki (supplementary)
Charge pump boost principle - this article will give you a simple understanding
Buildroot system for making raspberry pie cm3
Class of color image processing based on Halcon learning_ ndim_ norm. hdev
Sword finger offer 06 Print linked list from end to end
STM32 --- serial port communication
【论文阅读】2022年最新迁移学习综述笔注(Transferability in Deep Learning: A Survey)
Live555 push RTSP audio and video stream summary (I) cross compilation
【云原生 | 从零开始学Kubernetes】三、Kubernetes集群管理工具kubectl
Problem solving: interpreter error: no file or directory
Google sitemap files for rails Projects - Google sitemap files for rails projects
PMSM dead time compensation
[tutorial 19 of trio basic from introduction to proficiency] detailed introduction of trio as a slave station connecting to the third-party bus (anybus PROFIBUS DP...)