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

External link:

http://acm.hdu.edu.cn/showproblem.php?pid=3887

Posted by xiaodao
Category: HDU