代码内容讲得比较清晰，慢慢细品吧··
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<cstdlib> using namespace std; #define rep(i,l,r) for(i=l;i<=r;i++) #define ll long long const int INF = 0x7fffffff; const int N = 1e6 + 7; const int mod = 1e9 + 7; struct node { ll b; ll id; }h[N]; ll c[N]; vector<ll>G[N]; bool cmp(const node& a, const node& b) { if (a.b == b.b) return G[a.id].size() < G[b.id].size(); else return a.b > b.b; } ll n, m, t, x; ll vis[N]; ll cnt[N]; ll dis[N]; int main() { ll i, j, k; ll u, v; cin >> n >> k; rep(i, 1, n - 1) { cin >> u >> v; G[u].push_back(v); G[v].push_back(u); } memset(vis, 0, sizeof(vis)); x = 0; h[1].b = 0; rep(i, 1, n) { h[i].id = i; cnt[i] = 1; } vis[1] = 1; queue<ll>q; q.push(1); while (!q.empty()) { ll start = q.front(); q.pop(); for (i = 0; i < G[start].size(); i++) { if (!vis[G[start][i]]) { vis[G[start][i]] = 1; h[G[start][i]].b = h[start].b + 1;//计算深度 q.push(G[start][i]); } } } rep(i, 1, n) { dis[i] = h[i].b; } sort(h + 1, h + n + 1, cmp); for (i = 1; i <= n; i++) { int now = h[i].id; for (j = 0; j < G[now].size(); j++) { if (dis[G[now][j]] > dis[now]) cnt[now] += cnt[G[now][j]]; //计算该节点的儿子们所做的贡献，即当该节点被标记时，统计该点后面儿子们所失去的总贡献 // cout << cnt[now] << " " << cnt[G[now][j]]<<" "; } /* cout << endl;*/ h[i].b -= (cnt[now] - 1);//若该点被标记，减去儿子后面的所做的贡献，记得-1减去本身 } sort(h + 1, h + n + 1, cmp); ll ans = 0; rep(i, 1, k) { ans += h[i].b; } cout << ans << endl; } /* 20 7 9 7 3 7 15 9 1 3 11 9 18 7 17 18 20 1 4 11 2 11 12 18 8 18 13 2 19 2 10 9 6 13 5 8 14 1 16 13 */