### Brief description:

給定一棵樹，對於每個結點，詢問其子樹中結點標號小於其的數目。

### Analysis:

… 略）。。（。離線後參照 Apple Tree。。)。。

http://acm.hust.edu.cn/vjudge/problem/viewSource.action?id=1169143

const int N = 100009, M = 2 * N; int L[N], R[N], cnt; // Vertex .. . int hd[N], nxt[M], a[M], b[M]; // Adjacent List .. . int C[N]; // Interval Tree int n, root; void Modify(int x, int d){ while (x <= n) C[x] += d, x += low_bit(x); } int Sum(int x){ int res = 0; while (x) res += C[x], x ^= low_bit(x); return res; } int Sum(int l, int r){ return Sum(r) - Sum(l-1); } #define v b[i] inline void dfs(int u = root){ L[u] = ++cnt; for (int i=hd[u];i;i=nxt[i]) if (!L[v]){ dfs(v); } R[u] = cnt; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif while (scanf("%d %d", &n, &root) != EOF && n){ RST(hd, C, L), cnt = 0; FOR_C(i, 2, n << 1){ RD(a[i], b[i]), a[i|1] = b[i], b[i|1] = a[i]; nxt[i] = hd[a[i]], hd[a[i]] = i; ++i; nxt[i] = hd[a[i]], hd[a[i]] = i; } dfs(); REP_1(i, n){ OT(Sum(L[i], R[i])); if (i == n) puts(""); else printf(" "); Modify(L[i], 1); } } }