当前位置:网站首页>Affected tree (tree DP)
Affected tree (tree DP)
2022-07-05 08:28:00 【A Fusu in the mountains】
Original link
Title Description
Misha Found a binary tree , Its vertex numbers are from to . A binary tree is an acyclic connected bidirectional graph containing vertices and edges . Each vertex has at most one degree , And the root vertex is a vertex with a number , It has at most one degree .
Unfortunately , The roots are infected .
The number of times the following process occurs :
Misha Or choose one that is not infected ( It's not deleted ) The summit of , And delete it , All edges have an endpoint at this vertex , Or do nothing .
then , Infection spreads to every vertex connected by an edge to the infected vertex ( All infected vertices are still infected ).
because Misha There is not much time to think , Please tell him the maximum number of vertices he can save from infection ( Note that deleted vertices are not included in the save )
sample input
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
sample output
0
2
2
10
Algorithm
( Tree form dp)
This problem can be solved by maintaining a dp Arrays can be counted quickly Each point is used as the root node to reserve the maximum number of left subtrees or right subtrees , And finally pass dfs Update iterations in the process , Generate the final required answer .
It is worth noting that the order of the deletion point of the title and its subtree is from root to branch , But in the tree dp The statistical process should be carried out from branches and leaves to roots dp Array statistics , Because the last thing left is the branches and leaves of each layer , General tree dp The industry mainly counts in this way
Equation of state :
dp[u][0] = sum[l[u]] - 1 + max(dp[r[u]][1],dp[r[u]][0]);// Keep the left subtree
dp[u][1] = sum[r[u]] - 1 + max(dp[l[u]][1],dp[l[u]][0]);// Keep the right subtree
C++ Code
Time complexity 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];// Each point is used as the root node to reserve the maximum number of left subtrees or right subtrees
int sum[N],l[N],r[N];// With u The total number of people that can be reserved for the root node ,u The left and right nodes of the node
void pre_dfs(int u,int fa)// Preprocessing
{
sum[u] = 1;
for (int i = 0;i < g[u].size();i ++ ) {
int j = g[u][i];
if (j == fa) continue;
// Classic code , utilize dfs The law of specifies the left and right nodes respectively
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;// initialization
for(int i = 0;i < g[u].size();i ++ ){
int j = g[u][i];
if (j == fa) continue;
dfs(j,u);
// The last part dp Statistics
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;
}
边栏推荐
- 【NOI模拟赛】汁树(树形DP)
- Talk about the circuit use of TVs tube
- Example 002: the bonus paid by the "individual income tax calculation" enterprise is based on the profit commission. When the profit (I) is less than or equal to 100000 yuan, the bonus can be increase
- Several implementation schemes of anti reverse connection protection of positive and negative poles of power supply!
- STM32 virtualization environment of QEMU
- The firmware of the connected j-link does not support the following memory access
- Adaptive filter
- leetcode - 445. Add two numbers II
- 动力电池UL2580测试项目包括哪些
- STM32 single chip microcomputer -- debug in keil5 cannot enter the main function
猜你喜欢
STM32 single chip microcomputer -- debug in keil5 cannot enter the main function
Working principle and type selection of common mode inductor
QEMU STM32 vscode debugging environment configuration
[tutorial 15 of trio basic from introduction to proficiency] trio free serial communication
Step motor generates S-curve upper computer
Hardware 3 -- function of voltage follower
Example 001: the number combination has four numbers: 1, 2, 3, 4. How many three digits can be formed that are different from each other and have no duplicate numbers? How many are each?
Design a clock frequency division circuit that can be switched arbitrarily
STM32 single chip microcomputer - external interrupt
STM32---IIC
随机推荐
Sizeof (function name) =?
Hardware and software solution of FPGA key chattering elimination
Slist of linked list
动力电池UL2580测试项目包括哪些
Detailed explanation of SQL server stored procedures
WiFi wpa_ Detailed description of supplicant hostpad interface
Adaptive filter
Soem EtherCAT source code analysis attachment 1 (establishment of communication operation environment)
STM32 single chip microcomputer - bit band operation
Brief discussion on Buck buck circuit
[cloud native | learn kubernetes from scratch] III. kubernetes cluster management tool kubectl
Ble encryption details
Arduino uses nrf24l01+ communication
Imx6ull bare metal development learning 1-assembly lit LED
Let's briefly talk about the chips commonly used in mobile phones - OVP chips
List of linked lists
UE pixel stream, come to a "diet pill"!
Explication de la procédure stockée pour SQL Server
Relationship between line voltage and phase voltage, line current and phase current
Go dependency injection -- Google open source library wire