首页 > 代码库 > HDU 3887 Counting Offspring（DFS序）
HDU 3887 Counting Offspring（DFS序）
Counting Offspring
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3054 Accepted Submission(s): 1031
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 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
2011 Multi-University Training Contest 5 - Host by BNU
题意：求在一个有根节点的树中 每个节点的子树中有多少个小于改点的序号
DFS序找到每个节点的时间戳 用树状数组直接维护这个区间就可以了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cctype> 5 #include<cmath> 6 #include<cstring> 7 #include<map> 8 #include<set> 9 #include<queue>10 #include<vector>11 #include<algorithm>12 #include<string>13 #define ll long long14 #define eps 1e-1015 #define LL unsigned long long16 using namespace std;17 const int inf=0x3f3f3f3f;18 const int N=200000+10;19 const int mod=1e9+7;20 int head[N];21 int tot,time;22 int L[N],R[N];23 struct node{24 int to,next;25 }edge[N<<1];26 int a[N*5];27 void init(){28 memset(head,-1,sizeof(head));29 tot=0;30 time=0;31 }32 void add(int u,int v){33 edge[tot].to=v;34 edge[tot].next=head[u];35 head[u]=tot++;36 }37 void DFS(int x,int fa){38 L[x]=++time;39 for(int i=head[x];i!=-1;i=edge[i].next){40 int v=edge[i].to;41 if(v==fa)continue;42 DFS(v,x);43 }44 R[x]=time;45 46 }47 int lowbit(int x){48 return x&(-x);49 }50 void update(int x,int y){51 while(x<=time){52 a[x]=a[x]+y;53 x=x+lowbit(x);54 }55 }56 int getsum(int x){57 int ans=0;58 while(x>0){59 //cout<<2<<endl;60 ans=ans+a[x];61 x=x-lowbit(x);62 }63 return ans;64 }65 int main(){66 int n,p;67 while(scanf("%d%d",&n,&p)!=EOF){68 if(n==0&&p==0)break;69 init();70 memset(a,0,sizeof(a));71 for(int i=1;i<n;i++){72 int u,v;73 scanf("%d%d",&u,&v);74 add(u,v);75 add(v,u);76 }77 DFS(p,-1);78 for(int i=1;i<=n;i++){79 int ans=getsum(R[i])-getsum(L[i]-1);80 if(i!=n)cout<<ans<<" ";81 else{82 cout<<ans<<endl;83 }84 update(L[i],1);85 }86 }87 }
HDU 3887 Counting Offspring（DFS序）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。