HDU – 6203 ping ping ping LCA倍增算法+dfs序+线段树

ping ping ping LCA倍增算法+dfs序+线段树

 Source

HDU - 6203

My Solution

题意：给出一颗以0为根有n+1个节点的树，给出p个条件，每个条件表示u,v之间有一个坏的节点，根据这p个条件求出树上至少有多少坏点。

LCA倍增算法+dfs序+线段树

先跑出dfs序，并对LCA进行预处理。

然后把每组条件按照u,v的LCA为第一优先级丢到优先队列里，

且对于dfs序有个性质，如果P是U的祖先，则 p1[P] <= p1[U] <= p2[U] <= p2[P]，

故每次对于每个LCA(u,v),u,v ：

先判断 u，v是否存在被标记的祖先，如果都没有说明需要新标记一个点为坏点，即把LCA(u,v)标记，即用线段树把[p1[LCA(u,v), p2[LCA(u,v)]全部标记，并且ans++。

否则就是已经被坏点隔断了，直接处理下一个LCA(u,v),u,v

且这里是优先处理深度大的点，这样接下来的LCA必定是和已处理的并列或者深度小这样就不会被重复标记了。

时间复杂度 O((n+q)*logn)

空间复杂度 O(nlogn)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<int, int> ii;
typedef pair<int, pair<int, int>> iii;
const int MAXN = 1e4 + 8;

vector sons[MAXN];
int father[MAXN][22], depth[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;
        father[v][0] = u;
        depth[v] = depth[u] + 1;
        get_dfs_list(v, u);
    }
    p2[u] = ti;
}
//LCA
inline void prepare(int n){
    int i, j;
    for(j = 1; j <= 20; j++){
        for(i = 1; i <= n; i++){
            father[i][j] = father[father[i][j-1]][j-1];
        }
    }
}
inline int LCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int dc = depth[u] - depth[v];
    int i;
    for(i = 0; i <= 20; i++){
        if((1<<i) & dc) u = father[u][i]; } if(u == v) return u; for(i = 20; i >= 0; i--){
        if (father[u][i] != father[v][i]){
            u = father[u][i];
            v = father[v][i];
        }
    }
    u = father[u][0];
    return u;
}


//线段树
bool sum[4*MAXN], lazy[4*MAXN];
int size;
inline void pushup(int Ind){
    ;
}

inline void pushdown(int Ind){
    sum[Ind<<1] |= lazy[Ind];
    sum[(Ind<<1)|1] |= lazy[Ind];
    lazy[Ind<<1] |= lazy[Ind];
    lazy[(Ind<<1)|1] |= lazy[Ind]; lazy[Ind] = false; } inline bool _Query(int a, int l, int r, int Ind){ if(l == r && l == a) return sum[Ind]; int mid = (l+r)>>1;
    if(lazy[Ind]) pushdown(Ind);
    LL ret = 0;
    if(a <= mid) return _Query(a, l, mid, Ind<<1);
    else return _Query(a, mid + 1, r, (Ind<<1)|1);
}

inline void _Modify(int a, int b, int l, int r, int Ind, bool d){
     if(a <= l && b >= r){
        sum[Ind] |= d;
        lazy[Ind] |= d;
        return;
    }
    int mid = (l+r)>>1;
    if(lazy[Ind]) pushdown(Ind);
    if(a <= mid) _Modify(a, b, l, mid, Ind<<1, d); if(b > mid) _Modify(a, b, mid + 1, r, (Ind<<1)|1, d);
    //pushup(Ind);
}

inline LL Query(int a) {return _Query(a, 1, size, 1);}
inline void Modify(int a, int b, bool d){return _Modify(a, b, 1, size, 1, d);}

priority_queue pq;

int main()
{
    #ifdef LOCAL
    freopen("d.txt", "r", stdin);
    //freopen("d.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, m, i, u, v, uv, root, ans;
    while(cin >> n){
        for(i = 1; i <= n; i++){ cin >> u >> v;
            sons[u].push_back(v);
            sons[v].push_back(u);
        }
        root = 0;
        ti = 0;
        get_dfs_list(root, -1);
        size = ti;
        prepare(ti);
        cin >> m;
        while(m--){
            cin >> u >> v;
            pq.push(iii(depth[LCA(u, v)], ii(u, v)));
        }
        ans = 0;
        while(!pq.empty()){
            u = pq.top().second.first;
            v = pq.top().second.second;
            uv = LCA(u, v);
            pq.pop();
            if(!Query(p1[u]) && !Query(p1[v])){
                ans++;
                Modify(p1[uv], p2[uv], 1);
            }
        }
        cout << ans << "n";

        //resize
        for(i = 0; i <= n; i++){
            sons[i].clear();
        }
        memset(sum, 0, sizeof sum);
        memset(lazy, 0, sizeof lazy);
        memset(father, 0, sizeof father);
        memset(depth, 0, sizeof depth);
    }


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

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

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx