思路：我们可以很容易想到，最深的点可能是我们需要的点，我们选点都是从最深点考虑，但有种情况是，在最优的情况，我们选择了一个点建立工厂，这个点有两个儿子点，那这两个儿子也一定是工厂，这两个儿子工厂的价值会因为父亲节点建立了工厂随之减去1，这是难点，我们只需要把两个儿子的代价转移，保持两个儿子点的价值，把要失去的价值给父亲结点，就是父亲结点的价值减去两个儿子失去的价值2，这样维护每个节点价值，sort一下，选择前K个即可。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 #include <vector> 6 7 using namespace std; 8 9 #define fi first 10 #define se second 11 #define ll long long 12 #define pb push_back 13 14 const int N = (int)2e5 + 10; 15 struct Tree{ 16 int depth; 17 int son; 18 int value; 19 void cal(){ 20 value = depth - son; 21 } 22 bool friend operator<(const Tree& a, const Tree& b){ 23 return a.value > b.value; 24 } 25 }tree[N]; 26 vector<int > G[N]; 27 int n, k; 28 29 void process(int now, int pre){ 30 tree[now].son = 1; 31 tree[now].depth = tree[pre].depth + 1; 32 for(int to : G[now]){ 33 if(to == pre) continue; 34 process(to, now); 35 tree[now].son += tree[to].son; 36 } 37 tree[now].cal(); 38 } 39 40 void solve(){ 41 cin >> n >> k; 42 for(int i = 1; i < n; ++i){ 43 int u, v; 44 cin >> u >> v; 45 G[u].pb(v); 46 G[v].pb(u); 47 } 48 process(1, 0); 49 sort(tree + 1, tree + 1 + n); 50 ll ans = 0; 51 for(int i = 1; i <= k; ++i){ 52 ans += tree[i].value; 53 } 54 cout << ans << endl; 55 } 56 57 int main(){ 58 59 ios::sync_with_stdio(false); 60 cin.tie(0); 61 cout.tie(0); 62 solve(); 63 64 65 return 0; 66 }