Links: https://ac.nowcoder.com/acm/contest/1069/A
Source: Niuke.com

Time limit: C/C++ 1 second, 2 seconds for other languages
Space limitations: C/C++ 32768K, other languages 65536K
64bit IO Format: %lld
Title Description
Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1...N) so they can all communicate.
Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.
Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.
Enter a description:

• Line 1: A single integer: N
• Lines 2...N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B
  Output description:
• Line 1: A single integer indicating the minimum number of towers to install
  Example 1
  input
  copy

5
1 3
5 2
4 3
3 5

output
copy

2

Explain
The towers can be placed at pastures 2 and 3 or pastures 3 and 5.

1. Topic:

Given the edges that are directly connected, select the fewest points so that all points are covered (points can be covered if they are directly connected to all edges of the selected point)
This question essentially seeks the minimum dominant set.

2. The concept of minimum dominant set:

The definition of dominant set is as follows: given undirected graph G = (V, E), where V is a point set, E is an edge set, and a subset of V S is called a dominant set if and only if there is a point u in S for any point v in V-S, such that (u, v) < E.
In particular, the smallest dominant set S (that is, any set smaller than S cannot be a dominant set) is called the smallest dominant set

3. Solving the minimum dominant set:

1. Tarjan-like and dfs-based greed
2. Tree dp

4. Specific operations

Solution 1:
Greed:
1. Select one of the points as root, define the father array, and mark the root's father as himself.
2. Define a dfsn array to record the dfs order of each point when used for dfs
3.dfs, DFS gets the DFS order and the father for each point
4. Define an s-array as the container of the dominant set.
Reinitialize vis, which is used to mark whether it belongs to and is connected to points in the dominant set
Record answers: Select points in reverse order of dfs
For a point that either does not belong to or is not connected to a point in the dominant set
If his parent node does not belong to the dominant set, add its parent node to the dominant set, ans++, and mark that the parent node of the current node belongs to the dominant set s
Marks the parent node of the current node, the parent node of the current node (belonging to the dominant set), and the parent node of the parent node of the current node (connected to the points in the dominant set).

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+5;
vector<int>vec[MAXN];
int dfn[MAXN];
bool vis[MAXN];
int father[MAXN];
int s[MAXN];
int cnt;
int n;
void init()
{
    for(int i = 0; i<= n; i++)
    {
        vis[i] = false;
    }
}
void dfs(int s)
{
    dfn[++cnt] = s ;
    int iSize = vec[s].size();
    for(int i = 0; i < iSize; i++)
    {
        int to = vec[s][i];
        if(!vis[to])
        {
            father[to] = s;
            vis[to] = true;
            dfs(to);
        }
    }
    return;
}
int solve()
{
    father[1] = 1;
    vis[1] = true;
    dfs(1);
    init();
    int ans = 0;
    for(int i = cnt; i > 0; i--)
    {
        int x = dfn[i];
        if(!vis[x])//Does not belong to or connect to points in a dominant set
        {
            if(!s[father[x]])//Its parent node does not belong to the dominant set
            {
                ans++;
                s[father[x]] = true;//Parent Node Into Dominant Set
            }
            vis[x] = true;//Mark yourself
            vis[father[x]] = true;//Mark your own father
            vis[father[father[x]]] = true;//Mark your father's father
        }
    }
    return ans;
}
int main()
{
    cin>>n;
    int x,y;
    for(int i = 1; i < n; i++)
    {
        cin>>x>>y;
        vec[x].push_back(y);
        vec[y].push_back(x);
    }
    cout<<solve()<<endl;
    return 0;
}

Solution 2:
dp:(I mean not)
Refer to the following code from Baidu Encyclopedia:

#include<iostream> 
#include<cstdlib> 
#include<cstdio> 
#include<cmath> 
using namespace std; 
const int MAXN=10010; 
const int INF=int(1e7); 
struct node 
{ 
    int to; 
    int next; 
} edge[MAXN*2]; 
int head[MAXN*2],num; 
int dp[MAXN][3]; 
/* 
1):dp[i][0],Indicates that point i belongs to the dominant set,
And if the subtree rooted at point i is covered, the minimum number of points in the set will be dominated. 
2):dp[i][1],Indicates that point i does not belong to the dominant set and that subtrees rooted in i are covered.
Moreover, if i is covered by at least one of the subnodes, the minimum number of points in the dominant set is determined. 
3):dp[i][2],Indicates that point i does not belong to the dominant set,
And the subtree rooted in i is covered, and i is not covered by the child nodes. That is, i is covered by the parent node. 
*/ 
int n; 
void add(int x,int y) 
{ 
    edge[++num].next=head[x]; 
    edge[num].to=y; 
    head[x]=num; 
} 
void DP( int k,int fat ) 
{ 
    dp[ k ][ 0 ]=1; 
    dp[ k ][ 2 ]=0; 
    bool s=0; 
    int x,sum=0,inc=INF; 
    for(int i=head[ k ]; i ;i=edge[i].next ) 
    { 
        x=edge[i].to; 
        if( x==fat )    continue ; 
        DP( x,k ); 
        dp[ k ][ 0 ]+=min(dp[ x ][ 0 ],min(dp[ x ][ 1 ],dp[ x ][ 2 ])); 
        if( dp[ x ][ 0 ] <= dp[ x ][ 1 ] ) 
        { 
            sum+=dp[ x ][ 0 ]; 
            s=1; 
        } 
        else 
        { 
            sum+=dp[ x ][ 1 ]; 
            inc=min(inc,dp[ x ][ 0 ]-dp[ x ][ 1 ]); 
        } 
        if( dp[ x ][ 1 ]!=INF && dp[ k ][ 2 ]!=INF ) 
        //x is not a leaf node, and k has a father, that is, k is not a root  
            dp[ k ][ 2 ]+=dp[ x ][ 1 ]; 
        else 
            dp[ k ][ 2 ]=INF; 
    } 
    if( inc==INF && !s )//k has no child nodes     
        dp[ k ][ 1 ]=INF; 
    else 
    { 
        dp[ k ][ 1 ]=sum; 
        if( !s )//If it is not zero, one of k's children is already stained     
            dp[ k ][ 1 ]+=inc; 
    } 
    return ; 
} 
int main() 
{ 
    int u,v; 
    scanf("%d",&n); 
    for(int i=1; i<=n-1; i++) 
    { 
        scanf("%d%d",&u,&v); 
        add(u,v); 
        add(v,u); 
    } 
    DP( 1,0 ); 
    int ans=min(dp[1][0],dp[1][1]); 
    printf("%d\n",ans); 
    return 0;