HDU – 3887 Counting Offspring dfs序+线段树

Counting Offspring dfs序+线段树

 Source

HDU - 3887

My Solution

题意：问对于每个节点，它的子树上标号比它小的点有多少个。

dfs序+线段树

关于dfs序：

dfs序是处理树上问题很重要的一个工具，主要能够解决对于一个点，它的子树上的一些信息的维护，即用来处理子树的问题。 
dfs序一般开的空间是n，因为只在入的地方时间戳++，出来的地方时间戳没有额外的++，线段树的每个节点应当是时间戳。

这里，因为点在它的子树上，所以在线段树中，故在它的两个时间戳的区间内([p1[i],p2[i])，所以我们只需要从小到大考虑，它的区间里有多少个点已经放入，然后再把它放入即可。

时间复杂度 O(nlogn)

空间复杂度 O(4*n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

vector sons[MAXN];
//dfs序
int p1[MAXN], p2[MAXN], ti = 0;
int dfsnum[MAXN];  //这个按情况是否需要。
inline void get_dfs_list(int u, int fa){
    p1[u] = ++ti;
    dfsnum[ti] = u; //
    int sz = sons[u].size(), i, v;
    for(i = 0; i < sz; i++){
        v = sons[u][i];
        if(v == fa) continue;
        get_dfs_list(v, u);
    }
    p2[u] = ti;
}
//线段树
int sum[4*MAXN];
int size;
inline void pushup(int Ind){
    sum[Ind] = sum[Ind<<1] + sum[(Ind<<1) + 1];
}

inline int _Query(int a, int b, int l, int r, int Ind){
    if(a <= l && b >= r) return sum[Ind];
    int mid = (l+r)>>1; int ret = 0;
    if(a <= mid) ret += _Query(a, b, l, mid, Ind<<1); if(b > mid) ret += _Query(a, b, mid + 1, r, (Ind<<1) + 1); return ret; } inline void _Modify(int a, int l, int r, int Ind, int d){ if(l == r && l == a){ sum[Ind] = d; return; } int mid = (l+r)>>1;
    if(a <= mid) _Modify(a, l, mid, Ind<<1, d);
    else _Modify(a, mid + 1, r, (Ind<<1) + 1, d); pushup(Ind); } inline int Query(int a, int b) {return _Query(a, b, 1, size, 1);} inline void Modify(int a, int d){return _Modify(a, 1, size, 1, d);} int main() { #ifdef LOCAL freopen("a.txt", "r", stdin); //freopen("a.out", "w", stdout); int T = 1; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int n, p, i, u, v, root; while(cin >> n >> p){
        if(n == 0 && p == 0) break;
        for(i = 1; i < n; i++){ cin >> u >> v;
            sons[u].push_back(v);
            sons[v].push_back(u);
        }
        root = p;
        ti = 0;
        get_dfs_list(root, -1);
        size = ti;
        memset(sum, 0, sizeof sum);
        for(i = 1; i <= n; i++){
            cout << Query(p1[i], p2[i]);
            if(i == n) cout << "n";
            else cout << " ";
            Modify(p1[i], 1);
            sons[i].clear();
        }
    }



    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx