dfs序就是相当于把树转化成了一个区间，在区间上进行操作。
void dfs(int u, int fa) {
l[u]=++key;
for (int i=head[u]; i!=-; i=e[i].next) {
int v=e[i].v;
if (v!=fa) {
dfs(v, u);
}
}
r[u]=key;
}
hdu3887
题意：问你1-n这些节点的子节点下面有多少个比他小的节点。
其实仔细看跟树状数组的逆序数很像啊，算是dfs序的入门题了
从1-n分别对他们的所属的区间[l-1, r]进行操作，对l进行+1的操作。
因为对小的那个操作就相当于树状数组的逆序数的操作，就可以求出多少个比节点小的了。
/* gyt
Live up to every day */
#pragma comment(linker,"/STACK:1024000000,1024000000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<cstring>
#include<queue>
#include<set>
#include<string>
#include<map>
#include <time.h>
#define PI acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int maxn = ;
const ll maxm = 1e7;
const ll base = ;
const int INF = <<;
const db eps = 1e-;
const ll mod = 1e9+;
int l[maxn], r[maxn];
int key, cnt;
struct edge{
int u, v, next;
}e[maxn*];
int head[maxn];
int c[maxn];
int ans[maxn]; void init() {
key=; cnt=;
memset(c, , sizeof(c));
memset(l, , sizeof(l));
memset(r, , sizeof(r));
memset(ans, , sizeof(ans));
memset(head, -, sizeof(head));
}
void dfs(int u, int fa) {
l[u]=++key;
for (int i=head[u]; i!=-; i=e[i].next) {
int v=e[i].v;
if (v!=fa) {
dfs(v, u);
}
}
r[u]=key;
}
void add(int u, int v) {
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt++;
}
int lowbit(int x) {
return x&-x;
}
void updata(int x, int d) {
while(x<maxn) {
c[x]+=d;
x+=lowbit(x);
}
}
int getsum(int x) {
int ret=;
while(x>) {
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
void solve() {
int n, root;
while(scanf("%d%d", &n, &root)!=EOF) {
if (!n&&!root) break;
init();
for (int i=; i<n-; i++) {
int u, v; scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
dfs(root, -);
for (int i=; i<=n; i++) {
//cout<<r[i]<<" "<<l[i]<<endl;
ans[i]=getsum(r[i])-getsum(l[i]-);
//cout<<getsum(r[i])<<" " << getsum(l[i]-1)<<endl;
updata(l[i], );
}
for (int i=; i<=n; i++) {
if(i!=) printf(" ");
printf("%d", ans[i]);
}
puts("");
}
}
int main() {
int t = ;
//freopen("in.txt","r",stdin);
// freopen("gcd.out","w",stdout);
//scanf("%d", &t);
while(t--)
solve();
return ;
}