洛谷P2982 [USACO10FEB]慢下来Slowing down

题目大意：给出一棵树，节点有点权，求每个节点的祖先中点权小于该节点的结点的个数。
思路如下：
- 从根节点开始，对树进行深度优先遍历。
- 当进行到节点 i 时，有：
  - $\text{i}$ 的祖先们 $\text{Father[i]}$ 已经被访问过了，但还没有退出。
  - 其他节点或者已经被访问过并退出了，或者还没有被访问。
- 那么需要一个数据结构，维护那些已经被访问过了，但还没有退出的点权，支持查询小于特定值的元素的数量 。
- 可以使用树状数组或者线段树。
Code

#include <cstdio>

#include <cstring>

#define re register

#define GC getchar()

#define Clean(X,K) memset(X,K,sizeof(X))

#define Lowbit(X) (X&(-X))

int Qread () {

    int X =  ;    char C = GC ;

    while (C > '' || C < '') C = GC ;

    while (C >='' && C <='') {

        X = X *  + C - '' ;

        C = GC ;

    }

    return X ;

}

const int Maxn =  ;

int N ,  P_C[Maxn] , Ans[Maxn] , En =  , Head[Maxn] , T[Maxn];

struct Edge {

    int From_Where , Goto_Where , Next_Edge ;

};

Edge E[Maxn * ] ;

void Adg (int X , int Y) {

    E[++En].From_Where = X ;

    E[En].Goto_Where = Y ;

    E[En].Next_Edge = Head[X] ;

    Head[X] = En ;

}

void Add (int X , int K) {

    while (X <= N) {

        T[X] += K ;

        X += Lowbit(X) ;

    }

}

int Ask (int X) {

    int Ans =  ;

    while (X > ) {

        Ans += T[X] ;

        X -= Lowbit(X) ;

    }

    return Ans ;

}

void Super_Powerful_DFS (int X , int Lst) {

    Ans[P_C[X]] = Ask (P_C[X]) ;

    //printf ("%d %d %d\n" , X , P_C[X],Ans[P_C[X]]) ;

    Add (P_C[X] , ) ;

    for (re int i = Head[X] ; i ; i = E[i].Next_Edge ) {

        if (E[i].Goto_Where == Lst) continue ;

        Super_Powerful_DFS ( E[i].Goto_Where , X) ;

    }

    Add (P_C[X] , -) ;

}

int main () {

    //freopen ("P2982.in" , "r" , stdin) ;

    Clean (Ans , ) , Clean (Head , ) , Clean (T , ) , En =  ;

    N = Qread () ;

    for (re int i =  ; i < N ; ++ i) {

        int X = Qread () , Y = Qread () ;

        Adg (X , Y) , Adg (Y , X) ;

    }

    for (re int i =  ; i <= N; ++ i) {

        int X = Qread () ;

        P_C[X] = i ;

    }

    Super_Powerful_DFS (  , -) ;

    for (re int i =  ; i <= N; ++ i) printf ("%d\n" , Ans[i]) ;

    fclose (stdin) ;

    fclose (stdout);

    return ;

}

点击这里学习树状数组

秒客网

洛谷P2982 [USACO10FEB]慢下来Slowing down

Thanks ！