[UVa 1267]Network

 ?1 //It is made by Awson on 2017.9.16 ?2 #include <map> ?3 #include <set> ?4 #include <cmath> ?5 #include <ctime> ?6 #include <queue> ?7 #include <stack> ?8 #include <cstdio> ?9 #include <string> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define LL long long 16 #define Max(a, b) ((a) > (b) ? (a) : (b)) 17 #define Min(a, b) ((a) < (b) ? (a) : (b)) 18 #define Abs(a) ((a) < 0 ? (-(a)) : (a)) 19 using namespace std; 20 const int N = 1000; 21 ?22 int n, s, k, u, v; 23 struct tt { 24 ????int to, next; 25 }edge[N*2+5]; 26 int path[N+5], top; 27 ?28 int dep[N+5], fa[N+5]; 29 bool isleave[N+5]; 30 ?31 struct node { 32 ????int u, dist; 33 ????node () { 34 ????} 35 ????node (int _u,int _dist) { 36 ????????u = _u; dist = _dist; 37 ????} 38 ????bool operator < (const node & b) const{ 39 ????????return dist < b.dist; 40 ????} 41 }; 42 priority_queue<node>Q; 43 ?44 int get_father(int u, int kth) { 45 ????if (!kth) return u; 46 ????return get_father(fa[u], kth-1); 47 } 48 void dfs2(int u, int kth) { 49 ????isleave[u] = false; 50 ????if (!kth) return; 51 ????for (int i = path[u]; i; i = edge[i].next) 52 ????????dfs2(edge[i].to, kth-1); 53 } 54 void dfs(int u, int depth) { 55 ????dep[u] = depth; 56 ????for (int i = path[u]; i; i = edge[i].next) 57 ????????if (dep[edge[i].to] == -1) { 58 ????????????dfs(edge[i].to, depth+1); 59 ????????????fa[edge[i].to] = u; 60 ????????????isleave[u] = false; 61 ????????} 62 } 63 void add(int u, int v) { 64 ????edge[++top].to = v; 65 ????edge[top].next = path[u]; 66 ????path[u] = top; 67 } 68 void work() { 69 ????memset(path, 0, sizeof(path)); top = 0; 70 ????memset(dep, -1, sizeof(dep)); 71 ????memset(isleave, 1, sizeof(isleave)); 72 ????memset(fa, 0, sizeof(fa)); 73 ????scanf("%d%d%d", &n, &s, &k); 74 ????for (int i = 1; i < n; i++) { 75 ????????scanf("%d%d", &u, &v); 76 ????????add(u, v); add(v, u); 77 ????} 78 ????dfs(s, 0); 79 ????for (int i = 1; i <= n; i++) 80 ????????if (isleave[i] && dep[i] > k) { 81 ????????????Q.push(node(i,dep[i])); 82 ????????} 83 ????int ans = 0; 84 ????while (!Q.empty()) { ????????85 ????????while (!isleave[Q.top().u]) { 86 ????????????Q.pop(); 87 ????????????if (Q.empty()) break; 88 ????????} 89 ????????if (Q.empty()) break; 90 ????????int father = get_father(Q.top().u, k); 91 ????????dfs2(father, k); 92 ????????ans++; 93 ????} 94 ????printf("%d\n", ans); 95 } 96 int main() { 97 ????int t; 98 ????scanf("%d", &t); 99 ????while (t--)100 ????????work();101 ????return 0;102 }