# 某岛

… : "…アッカリ～ン . .. . " .. .
July 16, 2010

## HDU 3887. Counting Offspring

### 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];
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);
}
}
}