首页 > ACM题库 > HDU-杭电 > HDU 3887-Counting Offspring-DFS-[解题报告]HOJ
2015
04-13

HDU 3887-Counting Offspring-DFS-[解题报告]HOJ

Counting Offspring

问题描述 :

You are given a tree, it’s root is p, and the node is numbered from 1 to n. Now define f(i) as the number of nodes whose number is less than i in all the succeeding nodes of node i. Now we need to calculate f(i) for any possible i.

输入:

Multiple cases (no more than 10), for each case:
The first line contains two integers n (0<n<=10^5) and p, representing this tree has n nodes, its root is p.
Following n-1 lines, each line has two integers, representing an edge in this tree.
The input terminates with two zeros.

输出:

Multiple cases (no more than 10), for each case:
The first line contains two integers n (0<n<=10^5) and p, representing this tree has n nodes, its root is p.
Following n-1 lines, each line has two integers, representing an edge in this tree.
The input terminates with two zeros.

样例输入:

15 7
7 10
7 1
7 9
7 3
7 4
10 14
14 2
14 13
9 11
9 6
6 5
6 8
3 15
3 12
0 0

样例输出:

0 0 0 0 0 1 6 0 3 1 0 0 0 2 0

/*
分析:
    ╮(╯▽╰)╭,昨天晚上见到了这个题,今天上午两节
课,一下课就到实验室刷这个题,愣是WA+OLT了俩小时。最
后无比郁闷的去上下午的两节课了,有一节还是体育、中午
还牟吃饭T^T,晚上的课直接翘掉,终于搞定这个题了。
    树状数组很早就会了,你说我得有多菜,囧~~~
    还意外的上了第一版,囧~,虽然倒数第二吧,囧~

    思路:
        10W的数据,杭电OJ用DFS的话必须会爆,所以就自
    己手动模拟栈吧(人才培养方案关于程序的只有一门C的、
    数据结构都要自己学的人儿,桑不起呀囧~)。
        然后DFS的过程中,每个节点都会有两次作为当前节
    点的时候,仔细想想,这两次之间的过程所扫描到的点,
    必定都是其子孙节点。那么,记录第一、二次扫描到这
    个节点的时候,树状数组C中,在其前面并且比它小的点
    的数量,则:ans[i]=num2[i]-num1[i]。
        而树状数组,在每一个节点要退出栈的时候,以这
    个元素更新一次(注意,如果让树状数组C[i]表示“<=”i
    的元素个数的话,那么要先得到num2[i],然后再更新,
    否则会计算自己的)。

    PS:暂时不会神马Cplusplus的容器,所以用的静态临街
    表。我做了一个小优化,用eage_now[节点[i]]来记录当
    前该扫描节点[i]的哪一条边了,省的重复调用前面已经
    搜索过的边。弱菜很囧~~~

                                          2012-10-16
*/

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
int n,root;
int C[100011];
int ans[100011];
int hash[100011];
int queue[100011];
int eage_now[100011];
struct Eage
{
	int from,to,next;
}eage[200011];
int tot,head[100011];
void add(int a,int b)
{
	eage[tot].from=a;
	eage[tot].to=b;
	eage[tot].next=head[a];
	head[a]=tot++;
}
int query(int k)
{
	int t=0;
	while(k>0)
	{
		t+=C[k];
		k-=k&(-k);
	}
	return t;
}
void update(int k,int dir)
{
	while(k<=n && k>0)
	{
		C[k]+=dir;
		k+=k&(-k);
	}
}
void DFS()
{
	int z,i,j;
	int k=0;
	int flag;

	memset(hash,0,sizeof(hash));
	hash[root]=1;
	queue[++k]=root;
	ans[root]=0;
	for(i=0;i<=n;i++)	eage_now[i]=head[i];
	while(k)
	{
		flag=0;
		for(j=eage_now[queue[k]];j!=-1;j=eage[j].next)
		{
			z=eage[j].to;
			if(hash[z])	continue;
			eage_now[queue[k]]=eage[j].next;
			queue[++k]=z;
			hash[z]=1;
			ans[z]=query(z);
			flag=1;
			break;
		}
		if(flag==0)
		{
			ans[queue[k]]=query(queue[k])-ans[queue[k]];
			update(queue[k],1);
			k--;
		}
	}
}
int main()
{
	int i;
	int a,b;
	while(scanf("%d%d",&n,&root),n||root)
	{
		tot=0;
		memset(head,-1,sizeof(head));
		for(i=1;i<n;i++)	{scanf("%d%d",&a,&b);add(a,b);add(b,a);}

		memset(C,0,sizeof(C));
		DFS();

		for(i=1;i<n;i++)	printf("%d ",ans[i]);
		printf("%d\n",ans[n]);
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ice_crazy/article/details/8078711


, ,
  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c