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

云计算 waitig 678℃ 百度已收录 0评论

ping ping ping

 HDU
– 6203

The structure of the computer room in Northeastern University is pretty miraculous. There are n servers,
some servers connect to the gateway whose IP address is 0 directly. All servers are connected with each other by n netting
twines. It is said that this structure is favorable for maintaining physical problem of servers. 
But because of an unexpected rainstorm, the computer room was destroyed by a terrible thunderclap! 
Our maintainer Bittersweet found that many servers were not able to be visited, so he hurried to the computer room to lookup the reason. After several hours, Bittersweet realized that some net gape of servers were broken by thunderclap. However, there were
too many servers to find out all the broken net gapes quickly. So he came up with an idea to assess the damaged condition roughly. Bittersweet decided to turn on some servers and ping other servers randomly, then record the unsuccessful pairs of servers. 
Now he need a program to analyze the record to confirm what is the minimum 
   
 number of servers whose net gape was destroyed by thunderclap. Can you help him to complete this work? 

Input
There are at most 20 test cases. 
In each test case, the first line is an integer n (3n104 
           
, denoting the number of servers. The IP address of these servers is 1n 
   

Then follows n lines,
each line contains two integers u 
and v (0u,vn 
             
), denoting that the server whose IP address is u is
connected with the server whose IP address is v by
netting twine initially. 
After those, there is one line contains only an integer p (p50000 
         
), denoting the number that Bittersweet uses ping. 
Then follows p lines,
each line contains two integers U and V ,
denoting when using server U to
ping server V,
it returned unsuccessful. 
Output
A single integer xx in
a line, denoting at least xx servers
whose net gape were broken. 
Sample Input
4
1 0
4 2
2 0
3 2
2
1 3
2 1
Sample Output
1

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 <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
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<int> 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<iii> 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;
}

                                                                                                                                             ——from ProLights

  Thank you!


本文由【waitig】发表在等英博客
本文固定链接:HDU – 6203 ping ping ping LCA倍增算法+dfs序+线段树
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)