Affected tree (tree DP)

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)$

#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;
}