首页 > 代码库 > HDU 5927 Auxiliary Set (dfs)
HDU 5927 Auxiliary Set (dfs)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5927
题意：
给你一棵树，其中有一些’不重要‘的点，要是这些’不重要‘的点的子树中有两个重要的点的LCA是这个点，那么这个点就是重要的点。每次询问 问你重要的点有多少？
思路：
用不重要的点建图，要是这个不重要点上的相邻子树至少有两个有重要的点不在同一子树上，那么这个不重要的点才变成重要的点。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <map> 6 using namespace std; 7 const int N = 1e5 + 5; 8 vector <int> G[N]; 9 int d[N], a[N], par[N], d2[N], cnt, son[N]; 10 bool vis[N]; 11 //son[u]表示u节点相邻的子树个数 12 //原图：d[u]表示以u节点为root的子树节点个数 13 //不重要点建的图：d2[u]表示以u节点为root的子树节点个数 14 //cnt表示不重要的点的个数 15 16 void init(int n) { 17 for(int i = 1; i <= n; ++i) { 18 G[i].clear(); 19 vis[i] = false; 20 } 21 } 22 23 void dfs1(int u, int p) { 24 d[u] = 1; 25 par[u] = p; 26 son[u] = 0; 27 for(int i = 0; i < G[u].size(); ++i) { 28 int v = G[u][i]; 29 if(v == p) 30 continue; 31 dfs1(v, u); 32 d[u] += d[v]; 33 ++son[u]; 34 } 35 } 36 37 void dfs2(int u) { 38 d2[u] = 1; 39 vis[u] = true; 40 int num = 0, num2 = 0; 41 for(int i = 0; i < G[u].size(); ++i) { 42 int v = G[u][i]; 43 if(!vis[v]) 44 dfs2(v); 45 d2[u] += d2[v]; 46 if(d[v] > d2[v]) { 47 ++num; 48 } 49 num2++; 50 } 51 if(num + (son[u] - num2) > 1) //符合条件 (不同子树中重要点)>=2; 52 return ; 53 else 54 cnt++; 55 } 56 57 int main() 58 { 59 int t, n, m, u, v, q; 60 scanf("%d", &t); 61 for(int ca = 1; ca <= t; ++ca) { 62 scanf("%d %d", &n, &m); 63 init(n); 64 for(int i = 1; i < n; ++i) { 65 scanf("%d %d", &u, &v); 66 G[u].push_back(v); 67 G[v].push_back(u); 68 } 69 printf("Case #%d:\n", ca); 70 dfs1(1, 0); 71 init(n); 72 while(m--) { 73 scanf("%d", &q); 74 for(int i = 1; i <= q; ++i) { 75 scanf("%d", a + i); 76 vis[a[i]] = true; 77 } 78 for(int i = 1; i <= q; ++i) { 79 if(vis[par[a[i]]]) { 80 G[par[a[i]]].push_back(a[i]); 81 } 82 } 83 for(int i = 1; i <= q; ++i) { 84 vis[a[i]] = false; 85 } 86 cnt = 0; 87 for(int i = 1; i <= q; ++i) { 88 if(!vis[a[i]]) { 89 dfs2(a[i]); 90 } 91 } 92 for(int i = 1; i <= q; ++i) { 93 vis[a[i]] = false; 94 G[a[i]].clear(); 95 } 96 printf("%d\n", n - cnt); 97 } 98 } 99 return 0;100 }
HDU 5927 Auxiliary Set (dfs)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。