题目链接。
分析:
《训练指南》上的代码,写的不是一般的漂亮。贴之以珍藏。
#include <iostream> #include <vector> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; const int maxn = 1000 + 10; vector<int> g[maxn], nodes[maxn]; int fa[maxn], k, n; bool covered[maxn]; void dfs(int u, int f, int d){ fa[u] = f; int nc = g[u].size(); if(nc == 1 && d > k) nodes[d].push_back(u); for(int i=0; i<nc; i++){ int v = g[u][i]; if(v != f) dfs(v, u, d+1); } } void dfs2(int u, int f, int d){ covered[u] = true; int nc = g[u].size(); for(int i=0; i<nc; i++){ int v = g[u][i]; if(v != f && d < k) dfs2(v, u, d+1); } } int solve(){ int ans = 0; memset(covered, false, sizeof(covered)); for(int d=n-1; d>k; d--){ for(int i=0; i<nodes[d].size(); i++){ int u = nodes[d][i]; if(covered[u]) continue; int v = u; for(int j=0; j<k; j++) v=fa[v]; dfs2(v, -1, 0); ans++; } } return ans; } int main(){ int T, s, u, v; scanf("%d", &T); while(T--){ scanf("%d%d%d", &n, &s, &k); for(int i=0; i<=n; i++) {g[i].clear(); nodes[i].clear();} for(int i=0; i<n-1; i++){ scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(s, -1, 0); printf("%d\n", solve()); } return 0; }