Counting Offspring
问你对于每个节点，它的子树上标号比它小的点有多少个
/* 子树的问题，dfs序可以很轻松的解决，因为点在它的子树上，所以在线段树中，必定在它的两个时间戳的区间之间，所以我们只需要从小到大考虑，它的区间里有多少个点已经放了，然后再把它放进去。很容易的解决了 每行的最后一个数后面不要出输出多余的空格，否则会PE */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 100010 using namespace std; int n,p,num,head[maxn],xu[maxn],sz[maxn],opx,opl,opr; struct node{int to,pre;}e[maxn*2]; struct Node{int l,r,v;}tr[maxn<<4]; void Insert(int from,int to){ e[++num].to=to; e[num].pre=head[from]; head[from]=num; } void build(int l,int r,int k){ tr[k].l=l;tr[k].r=r;tr[k].v=0; if(l==r)return; int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); } int id; void dfs(int now,int father){ xu[now]=++id; sz[now]=1; for(int i=head[now];i;i=e[i].pre){ int to=e[i].to; if(to==father)continue; dfs(to,now); sz[now]+=sz[to]; } } int query(int l,int r,int k){ if(l>=opl&&r<=opr){return tr[k].v;} int mid=(l+r)>>1; int res=0; if(opl<=mid)res+=query(l,mid,k<<1); if(opr>mid)res+=query(mid+1,r,k<<1|1); return res; } void change(int l,int r,int k){ if(l==r){tr[k].v++;return;} int mid=(l+r)>>1; if(opx<=mid)change(l,mid,k<<1); else change(mid+1,r,k<<1|1); tr[k].v=tr[k<<1].v+tr[k<<1|1].v; } int main(){ freopen("Cola.txt","r",stdin); while(1){ scanf("%d%d",&n,&p); if(n==0&&p==0)return 0; memset(head,0,sizeof(head)); memset(e,0,sizeof(e));num=0; id=0;build(1,n,1); int x,y; for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); Insert(x,y);Insert(y,x); } dfs(p,0); for(int i=1;i<=n;i++){ opl=xu[i],opr=xu[i]+sz[i]-1; if(i!=n)printf("%d ",query(1,n,1)); else printf("%d",query(1,n,1)); opx=xu[i]; change(1,n,1); } puts(""); } }