首页 > 代码库 > HDU3887 Counting Offspring [2017年6月计划 树上问题03]
HDU3887 Counting Offspring [2017年6月计划 树上问题03]
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.
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 77 107 17 97 37 410 1414 214 139 119 66 56 83 153 120 0
Sample Output
0 0 0 0 0 1 6 0 3 1 0 0 0 2 0
Author
bnugong
Source
2011 Multi-University Training Contest 5 - Host by BNU
Recommend
lcy | We have carefully selected several similar problems for you: 3450 1166 3030 1541 3743
//====================================
被格式错误卡了半个小时
开始多了空格，去了空格，不对
后来发现多组数据要加空行，然后在数据之间加了空行，不对
看了看题解才发现末尾要多一个空行
竟无语凝噎
//====================================
跟树状数组求逆序对的思想类似，大家可以去看那一道题的思路
#include <bits/stdc++.h>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;}
HDU3887 Counting Offspring [2017年6月计划 树上问题03]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。