非树形DP做法 （贪心）

由于整个图是一个树形结构，且起点固定为 $ss$ 那么与 $ss$ 相邻的点就必然不去，于 $ss$ 距离为 $22$ 的点可选择是否去。

贪心的思路是叶子节点必选，往上可选节点必选一定可以构造出最优解（最优解不唯一但能保证是其中一个最优解）。

证明如下：

①树形结构中的叶子节点是必选的：如果叶子节点的父节点仅有一个子节点，那么选择叶子节点或他本身对结果不造成影响。如果父节点有多个子节点，那么就可以去所有叶子节点，如果去父节点就只能去一个节点。因此子节点必选。

②去的城市尽量深一定能构造出最优解：把每个与起点 $ss$ 距离为 $22$ 的节点视为深度是 $00$ ，深度深的节点被选之后我们假设切掉不能继续选择节点的子树，剩下的可选择的空间一定是更大，更大的空间一定能构造最优解。

具体实现方法如代码：

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9+7;

vector<int> g[510000];
int n , s , dp[510000];

bool dfs(int x , int f) {
    int cnt = 0 , res = 0 , sum = 0;
    for (auto nxt : g[x]) {
        if (nxt != f) {
            res += dfs(nxt,x);
            sum += dp[nxt];
            cnt ++;
        }
    }
    if (res) {
        dp[x] = sum;
        return false;
    }
    if (cnt == 0) dp[x] = 1;
    dp[x] = sum+1;
    return true;
}

int main() {
    scanf("%d%d",&n,&s);
    for (int i = 1 ; i < n ; i ++) {
        int f , t;
        scanf("%d%d",&f,&t);
        g[f].push_back(t);
        g[t].push_back(f);
    }
    vector<int> pr;
    for (int i : g[s]) {
        pr.push_back(i);
    }
    int res  = 0;
    for (int i : pr) {
        for (int j : g[i]) {
            if (j != s) {
                dfs(j,i);
                res += dp[j];
            }
        }
    }
    printf("%d\n",res+1);
}