Counting Offspring

Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 2809    Accepted Submission(s): 981

Problem Description

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.

 

 

Input

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.

 

 

Output

For each test case, output n integer in one line representing f(1), f(2) … f(n), separated by a space.

 

 

Sample Input

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

 

 

Sample Output

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

 

 

Author

bnugong

 

 

Source

 

 

Recommend

lcy   |   We have carefully selected several similar problems for you:            

 

//====================================

被格式错误卡了半个小时

开始多了空格，去了空格，不对

后来发现多组数据要加空行，然后在数据之间加了空行，不对

看了看题解才发现末尾要多一个空行

 

竟无语凝噎

//====================================

 

跟树状数组求逆序对的思想类似，大家可以去看那一道题的思路

 

#include 
      
       inline void read(int &x){	char ch = getchar();char c = ch;x = 0;	while(ch < '0' || ch > '9')c = ch, ch = getchar();	while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();	if(c == '-')x = -x;}inline int lowbit(int &a){return a & (-a);}const int MAXN = 500000 + 10;int n,root,tmp1,tmp2;struct Edge{int u,v,next;}edge[MAXN << 1];int head[MAXN], cnt, l[MAXN << 1], r[MAXN << 1], bit[MAXN << 1];inline void insert(int a, int b){edge[++cnt] = Edge{a,b,head[a]};head[a] = cnt;}int b[MAXN], stack[MAXN], top, rank;void dfs(int root){	register int u,v,pos;	stack[++top] = root;	b[root] = 1;	while(top)	{		u = stack[top--];		if(l[u])		{			r[u] = ++rank;			continue;		}		stack[++top] = u;		l[u] = ++rank;		for(pos = head[u];pos;pos = edge[pos].next)		{			v = edge[pos].v;			if(b[v])continue;			b[v] = true;			stack[++top] = v;		}	}}inline void modify(int p, int k){	register int tmp = n << 1;	for(;p <= tmp;p += lowbit(p))		bit[p] += k;}inline int ask(int p){	register int ans = 0;	for(;p;p -= lowbit(p))		ans += bit[p];	return ans;}bool ok;int main(){	while(true)	{		read(n);read(root);		if(!(n || root))break;		memset(edge, 0, sizeof(edge));		memset(head, 0, sizeof(head));		memset(l, 0, sizeof(l));		memset(r, 0, sizeof(r));		cnt = 0;		memset(bit, 0, sizeof(bit));		memset(b, 0, sizeof(b));		memset(stack, 0, sizeof(stack));		top = 0;		rank = 0;		register int i;		for(i = 1;i < n;++ i)		{			read(tmp1);read(tmp2);			insert(tmp1, tmp2);			insert(tmp2, tmp1);		}		dfs(root);		printf("%d", ask(r[1]) - ask(l[1] - 1));		modify(l[1], 1);		for(i = 2;i <= n;i ++)		{			printf(" %d", ask(r[i]) - ask(l[i] - 1));			modify(l[i], 1);		}		printf("\n");	}	return 0;}