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

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

ping ping ping

– 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? 

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. 
A single integer xx in
a line, denoting at least xx servers
whose net gape were broken. 
Sample Input
1 0
4 2
2 0
3 2
1 3
2 1
Sample Output

HDU - 6203

My Solution
且对于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++。
时间复杂度 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];
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;
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;
    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);

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;
    #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;
        root = 0;
        ti = 0;
        get_dfs_list(root, -1);
        size = ti;
        cin >> m;
            cin >> u >> v;
            pq.push(iii(depth[LCA(u, v)], ii(u, v)));
        ans = 0;
            u = pq.top().second.first;
            v = pq.top().second.second;
            uv = LCA(u, v);
            if(!Query(p1[u]) && !Query(p1[v])){
                Modify(p1[uv], p2[uv], 1);
        cout << ans << "\n";

        for(i = 0; i <= n; i++){
        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!

本文固定链接:HDU – 6203 ping ping ping LCA倍增算法+dfs序+线段树
点赞 (0)分享 (0)