做树状数组专题，竟然还是没有看出这题可以用树状数组来写，表示有点不好意思啊。

原来树状数组之所以能够搞定这一题是因为我们在建立好一棵数时，通过反问一个节点的子孙们后，顺序对的变化数来统计有多少数字比该节点小的子孙节点。

该题用DFS搜索直接爆栈，所以恶心的写了一个模拟栈，其实要注意的就是每个节点要在第一次出栈时保留在栈，第二次才从栈中出去，亦即是当其孩子节点都被反问完之后。

这题还有一点不得不说的就是给定的边的关系没有确定，要建立一个双向的邻接表，这就相对与给定的点可以从不同的方向来看其从属关系，而给定的根节点就确定了这种关系。

代码如下：

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #define INF 10000000 #define MAXN 100005 using namespace std; struct Node {
   int code, next; }edge[2*MAXN]; int N, M, head[MAXN], tol, res[MAXN], c[MAXN], visit[MAXN]; stack
         
          stk; inline int lowbit(int x) {
   return x & -x; } inline void update(int pos, int val) {
   for (int i = pos; i <= N; i += lowbit(i))     {
           c[i] += val;     } } inline int getsum(int pos) {
   int s = 0; for (int i = pos; i > 0; i -= lowbit(i))         s += c[i]; return s; } void modify(int a, int b) {
       edge[tol].code = b;     edge[tol].next = head[a];     head[a] = tol++; } void dfs(int f) {
   int pos, code;     stk.push(f); while (!stk.empty())     {
   int pos = stk.top(); if (visit[pos])         {
               stk.pop();             res[pos] = getsum(pos-1) - res[pos];             update(pos, 1);         } else         {
               visit[pos] = 1;             res[pos] = getsum(pos-1); for (int i = head[pos]; i != -1; i = edge[i].next)             {
                   code = edge[i].code; if (!visit[code])                     stk.push(code);             }         }     } } int main() {
   int a, b; while (scanf("%d %d", &N, &M), M|N)     {
           tol = 0;         memset(head, -1, sizeof (head));         memset(c, 0, sizeof (c));         memset(visit, 0, sizeof (visit)); for (int i = 1; i < N; ++i)         {
               scanf("%d %d", &a, &b);             modify(a, b);             modify(b, a);         }         dfs(M); for (int i = 1; i <= N; ++i)         {
               printf(i == N ? "%d\n" : "%d ", res[i]);         }     } return 0; }