HDU 5927 Auxiliary Set

2019-11-08 18:25:51

字体：大中小

来源：转载

供稿：网友

Auxiliary Set

Time Limit: 9000/4500 MS (java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1171 Accepted Submission(s): 366PRoblem DescriptionGiven a rooted tree with n vertices, some of the vertices are important.An auxiliary set is a set containing vertices satisfying at least one of the two conditions：∙It is an important vertex∙It is the least common ancestor of two different important vertices.You are given a tree with n vertices (1 is the root) and q queries.Each query is a set of nodes which indicates the unimportant vertices in the tree. Answer the size (i.e. number of vertices) of the auxiliary set for each query.InputThe first line contains only one integer T (T≤1000), which indicates the number of test cases.For each test case, the first line contains two integers n (1≤n≤100000), q (0≤q≤100000).In the following n -1 lines, the i-th line contains two integers ui,vi(1≤ui,vi≤n) indicating there is an edge between uii and vi in the tree.In the next q lines, the i-th line first comes with an integer mi(1≤mi≤100000) indicating the number of vertices in the query set.Then comes with mi different integers, indicating the nodes in the query set.It is guaranteed that ∑qi=1mi≤100000.It is also guaranteed that the number of test cases in which n≥1000 or ∑qi=1mi≥1000 is no more than 10. OutputFor each test case, first output one line "Case #x:", where x is the case number (starting from 1).Then q lines follow, i-th line contains an integer indicating the size of the auxiliary set for each query. Sample Input

16 36 42 55 41 55 33 1 2 31 53 3 1 4 Sample OutputCase #1:363HintFor the query {1，2, 3}:•node 4, 5, 6 are important nodes For the query {5}：•node 1，2, 3, 4, 6 are important nodes•node 5 is the lea of node 4 and node 3 For the query {3, 1，4}:• node 2, 5, 6 are important nodes  
题意：树中有n个点，从1到n依次标记，其中1为根。
树中的点是否为一个satisfying的点，需要满足以下条件中的一个：
1、该点是一个important的点
2、该点有多于2个important点的子孙
问有多少个satisfying的点。
思路：dfs跑一遍，统计好每个节点的父节点、孩子数以及深度，根据深度对unimportant的节点排序，从最深层的unimportant节点遍历。具体看代码吧，代码有注释，写的很全了。
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <algorithm>using namespace std;#define SIZE  100000+10int T;//测试数int Case;int n;//节点数int q;//询问数int u,v;int un;vector<int> vertice[SIZE];//存放有关联的点int father[SIZE];//存放其父节点int son[SIZE];//存放儿子节点的个数int deep[SIZE];//存放节点的深度int unver[SIZE];//存放unimportant节点int unson[SIZE];//存放unimportant节点的儿子数void dfs(int ver, int fver, int d){//ver:当前节点 fver:其父节点 d:当前深度	father[ver] = fver;	deep[ver] = d;	int temp = vertice[ver].size();//与ver节点有关的节点数	if(ver == 1)//若节点为1，其没有父节点，儿子数即与其有关的节点的个数；		son[ver] = temp;	else//否则减去父节点		son[ver] = temp - 1;	for(int i=0; i<temp; i++)	{		int ver_1 = vertice[ver][i];		if(ver_1 == fver)			continue;		dfs(ver_1, ver, d+1);	}}bool cmp(int a, int b){	return deep[a] > deep[b];}void Initial(){	for(int i=0; i<=n; i++)		vertice[i].clear();}int main(){	scanf("%d",&T);	Case = 1;	while(T--)	{		printf("Case #%d:/n",Case++);		scanf("%d %d",&n,&q);		Initial();		for(int i=1;i<n;i++)		{			cin>>u>>v;			vertice[u].push_back(v);			vertice[v].push_back(u);		}		dfs(1,0,0);		for(int i=0;i<q;i++)		{			scanf("%d",&un);			for(int j=0; j<un; j++)			{				scanf("%d",&unver[j]);				unson[unver[j]]=son[unver[j]];			}			sort(unver, unver+un, cmp);//按深度对节点排序			int num = n-un;			for(int j=0; j<un; j++)			{//节点是从最深处开始遍历			 //则一个节点的孩子一定都是important节点				if(unson[unver[j]]>=2)					num++;				else if(unson[unver[j]] == 0)				{//该节点为叶子节点，那么父节点相当于没有这个孩子					unson[father[unver[j]]]--;				}			}			printf("%d/n",num);		}	}	return 0;}