单位建设网站申请报告,网站如何做cc防护,江门网站制作专业,3d装修效果图制作软件题目连接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid3887 题意#xff1a;给出一棵树#xff0c;对于每一个节点#xff0c;问他的子孙节点中有多少个节点小于该节点。 思路#xff1a;首先找出这棵树的DFS序列#xff0c;每一个节点出现在两个位置#xff…题目连接http://acm.hdu.edu.cn/showproblem.php?pid3887 题意给出一棵树对于每一个节点问他的子孙节点中有多少个节点小于该节点。 思路首先找出这棵树的DFS序列每一个节点出现在两个位置这两个位置之间的节点就是该节点的子孙节点。 然后用树状数组求出这两个位置之间有多少个节点小于该节点。 hdu这题出的有点龊 用dfs搜索会爆栈要手动模拟先序或者后序遍历 code: View Code 1 # includestdio.h 2 # includestring.h 3 # define N 100050 4 struct node{ 5 int from,to,next; 6 }edge[2*N],edge1[2*N]; 7 int head[N],tol,head1[N],tol1,S[N],s[N],k,dp[N],count[N],visit[N],sig[N]; 8 void add(int a,int b) 9 { 10 edge[tol].froma;edge[tol].tob;edge[tol].nexthead[a];head[a]tol; 11 } 12 void add1(int a,int b) 13 { 14 edge1[tol1].froma;edge1[tol1].tob;edge1[tol1].nexthead1[a];head1[a]tol1; 15 } 16 void dfs2(int root) 17 { 18 int j,top,u,v; 19 top0; 20 k0; 21 S[top]root; 22 while(top0) 23 { 24 uS[top]; 25 if(!visit[u]) 26 { 27 visit[u]1; 28 s[k]u; 29 sig[u]k; 30 } 31 for(jhead[u];j!-1;jedge[j].next) 32 { 33 vedge[j].to; 34 if(visit[v]) continue; 35 S[top]v; 36 break; 37 } 38 if(j-1) 39 { 40 top--; 41 dp[u]k-sig[u]; 42 } 43 } 44 } 45 void insert(int i) 46 { 47 while(ik) 48 { 49 count[i]; 50 ii(-i); 51 } 52 } 53 int query(int i) 54 { 55 int sum0; 56 while(i0) 57 { 58 sumcount[i]; 59 i-i(-i); 60 } 61 return sum; 62 } 63 int main() 64 { 65 int i,j,v,n,root,num[N],ans,node,a,b; 66 while(scanf(%d%d,n,root)!EOF) 67 { 68 if(!n !root) break; 69 tol0; 70 memset(head,-1,sizeof(head)); 71 for(i1;in;i) 72 { 73 scanf(%d%d,a,b); 74 add(a,b); 75 add(b,a); 76 } 77 memset(dp,0,sizeof(dp)); 78 //dfs1(root,0);//树形DP求节点子孙的个数 79 memset(visit,0,sizeof(visit)); 80 dfs2(root);//模拟栈先序遍历 81 tol10; 82 memset(head1,-1,sizeof(head1)); 83 for(i1;in;i) 84 { 85 nodes[i]; 86 ansdp[node]i; 87 add1(ans,node); 88 } 89 memset(count,0,sizeof(count)); 90 for(i1;in;i) 91 { 92 nodes[i]; 93 num[node]query(node-1); 94 insert(node); 95 for(jhead1[i];j!-1;jedge1[j].next) 96 { 97 vedge1[j].to; 98 num[v]query(v-1)-num[v]; 99 }100 }101 printf(%d,num[1]);102 for(i2;in;i)103 printf( %d,num[i]);104 printf(\n);105 }106 return 0;107 } 转载于:https://www.cnblogs.com/183zyz/archive/2011/09/30/2196452.html
