Counting Offspring
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 423 Accepted Submission(s): 137
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
题意是，给一棵树，给每个结点一个标号，问所有存在的结点，它的子树中，结点标号小于它的有多少个。
做法：DFS序列构造＋树状数组查询区间。
竟然忘了DFS的遍历的意义。对一棵树进行DFS遍历，一个结点最多到达两次，一次出，一次入，而这之间的结点标号均为它的子树结点的标号。所以只要用某种方法快速查询其左右标号内含的区间中，比它小的标号个数即可。（别＊2）在肖神的提携下，ym到了树状数组在本题的使用方法。
做法流程。初始化（记得树状数组和DFS记录序列要开点数*2的。。因为这个nc半天，不解释。） －>建图－> DFS（因为HDU坑爹的栈大小，必须手写栈模拟DFS才能过。。第一次手工模拟DFS。。太蛋疼了。。调了无数次。）－>对于每个点查询DFS序列。（既然是离线查询，那么就按照从小到大查吧。凡事要有个序，有序了就好查了。对于每个点的标号，先查它的左右区间是否有比它小的sum(r[i] - 1) - sum(l[i]]).....再把它插入树状数组中，插一次就好，不然结果还得除二。（都是肖神！）
T_T。。记得树状数组和dfs序列都是开到点数*2的，而其他的都是点数大小的。注意初始化和树状数组查询和更新时的范围同理。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;
stack <int> S;
#define maxn 100005
int cnt,p,n,tot,lit[maxn],seq[maxn * 2],l[maxn],r[maxn],tr[maxn * 2];
int bit(int x){return x & -x;}
bool vis[maxn];
struct edge
{
int p,next;
edge(){}
edge(int a,int b):p(a),next(b){}
}v[maxn],e[maxn * 2];
void add(int p,int q)
{
e[tot] = edge(q,v[p].next);
v[p].next = tot++;
}
int sum(int x)
{
int ans = 0;
for(;x > 0;x -= bit(x))
ans += tr[x];
return ans;
}
void mod(int x,int val)
{
for(;x < cnt;x += bit(x))
tr[x] += val;
}
void init()
{
tot = 0;
for(int i = 1;i <= n;i++)
v[i].next = -1;
fill(tr,tr + 2 * n + 1,0);
fill(vis,vis + n + 1,0);
while(!S.empty())
S.pop();
}
void dfs()
{
cnt = 1;
S.push(p);
while(!S.empty())
{
int now = S.top();
if(!vis[now])
{
seq[cnt] = now;
l[now] = cnt++;
vis[now] = true;
}
bool mark = false;
for(int k = v[now].next;~k;k = e[k].next)
{
if(!vis[e[k].p])
{
mark = true;
S.push(e[k].p);
v[now].next = e[k].next;
break;
}
}
if(mark)
continue;
if(vis[now])
{
seq[cnt] = now;
r[now] = cnt++;
S.pop();
}
}
}
void gao()
{
for(int i = 1;i <= n;i++)
{
lit[i] = sum(r[i] - 1) - sum(l[i]);
mod(l[i],1);
}
}
int main()
{
while(scanf("%d %d",&n,&p) == 2 && (p || n))
{
init();
for(int i = 0;i < n - 1;i++)
{
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
add(b,a);
}
dfs();
gao();
for(int i = 1;i <= n;i++)
{
printf("%d",lit[i]);
putchar((i == n)?'\n':' ');
}
}
}
Down