zstu3999——邻接表
Description
多组测试数据 给你一棵树，n个点(n<=10000),树的根为root(root<=n),然后有Q个询问，每个询问输入一个数x，求以x为根的子树有多少个点？Input
每组的第一行是一个整数n和一个整数root 接下来n-1行是这棵树的n-1条边，每行两个数a b，代表a点和b点之间有一条边 然后是一个整数Q，代表询问的数量 最后Q行每行是一个整数(Q<=n)Output
对于每个询问，输出以当前点为根的子树的节点总数Sample Input
3 1 1 2 1 3 1 1
Sample Output
3
HINT
Source
No_stop
#include
#include
#include
#include
using namespace std;
const int maxn = 10100;
int mark[maxn],cot[maxn];
vector G[10100];
int dfs(int root)
{mark[root] = 1;if(G[root].size() == 0){cot[root] = 1;return 1;}vector:: iterator endd = G[root].end();for(vector:: iterator i = G[root].begin(); i!= endd; i++){if(mark[*i]) continue;cot[root] += dfs(*i);}cot[root]++;return cot[root];
}
int main()
{int n,m,q,x;int a,b;while(~scanf("%d%d",&n,&m)){memset(mark,0,sizeof(mark));memset(cot,0,sizeof(cot));for(int i = 1; i < n ;i++){scanf("%d%d",&a,&b);G[a].push_back(b);G[b].push_back(a);}dfs(m);scanf("%d",&q);for(int i = 1; i <= q; i++){scanf("%d",&x);printf("%d\n",cot[x]);}for(int i = 1; i <= n;i++)G[i].clear();}return 0;
}
转载于:https://www.cnblogs.com/zero-begin/p/4502201.html
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！