HDU 4366 Successor（dfs序 + 分块）题解

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：每个人都有一个上司，每个人都有能力值和忠诚值，0是老板，现在给出m个询问，每次询问给出一个x，要求你找到x的所有直系和非直系下属中能力比他高的最忠诚的人是谁

思路：因为树上查询很麻烦，所以我们直接dfs序把关系变成线性。然后我们再分块，把每个块按照能力值升序排列，这样我们就能直接二分查找这个块内能力值大于x的数就是二分出来的数到块末尾的所有数。但是怎么查找最忠诚的？我们直接预处理每个块内i位置到块末尾的最忠诚人的位置就行了。

代码：

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<queue>

#include<vector>

#include<string>

#include<cstdio>

#include<cstring>

#include<sstream>

#include<iostream>

#include<algorithm>

typedef long long ll;

using namespace std;

const int maxn =  + ;

const int MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

struct node{

    int name, loyalty, ability;

    bool operator < (const node &x) const{

        return ability < x.ability;

    }

}p[maxn];

int loyalty[maxn], ability[maxn];

int in[maxn], out[maxn];    //在dfs序列中的位置1-id

int belong[maxn], id;

int head[maxn], tot;

struct Edge{

    int to, next;

}edge[maxn];

void init(){

    tot = id = ;

    memset(head, -, sizeof(head));

}

void addEdge(int u, int v){

    edge[tot].to = v;

    edge[tot].next = head[u];

    head[u] = tot++;

}

void dfs(int u){

    in[u] = ++id;

    p[id].ability = ability[u], p[id].loyalty = loyalty[u], p[id].name = u;

    for(int i = head[u]; i != -; i = edge[i].next){

        int v = edge[i].to;

        dfs(v);

    }

    out[u] = id;

}

int MaxLoy[maxn];    //从位置j到所属块末尾的最大loyalty的人在dfs序列的位置

int n, m, block, sz;

int solve(int x){

    int l = belong[in[x]], r = belong[out[x]];

    int L, R;

    int MaxLoyalty = -, ans = -;

    L = block * (l - ) + , R = min(L + block - , id);

    for(int i = L; i <= R; i++){

        if(in[p[i].name] > in[x] && out[p[i].name] <= out[x]){

            if(p[i].loyalty > MaxLoyalty && p[i].ability > ability[x]){

                MaxLoyalty = p[i].loyalty;

                ans = p[i].name;

            }

        }

    }

    L = l + , R = r - ;

    node c;

    c.ability = ability[x];

    for(int i = L; i <= R; i++){

        int s = block * (i - ) + , e = s + block;

        int pos = upper_bound(p + s, p + e, c) - p;

        if(pos >= e) continue;

        int tmp = MaxLoy[pos];

        if(p[tmp].loyalty > MaxLoyalty){

            MaxLoyalty = p[tmp].loyalty;

            ans = p[tmp].name;

        }

    }

    L = block * (r - ) + , R = min(L + block - , id);

    for(int i = L; i <= R; i++){

        if(in[p[i].name] > in[x] && out[p[i].name] <= out[x]){

            if(p[i].loyalty > MaxLoyalty && p[i].ability > ability[x]){

                MaxLoyalty = p[i].loyalty;

                ans = p[i].name;

            }

        }

    }

    return ans;

}

int main(){

    int T;

    scanf("%d", &T);

    while(T--){

        init();

        int a;

        scanf("%d%d", &n, &m);

        ability[] = -, loyalty[] = -;

        for(int i = ; i <= n - ; i++){

            scanf("%d%d%d", &a, &loyalty[i], &ability[i]);

            addEdge(a, i);

        }

        dfs();

        block = (int)sqrt(id * 1.0);

        for(int i = ; i <= id; i++){

            belong[i] = (i - ) / block + ;

        }

        sz = belong[id];

        for(int i = ; i <= sz; i++){

            int s = block * (i - ) + , e = min(s + block, id + );

            sort(p + s, p + e);

            int Max = -, pos;

            for(int j = e - ; j >= s; j--){

                if(Max < p[j].loyalty){

                    Max = p[j].loyalty;

                    pos = j;

                }

                MaxLoy[j] = pos;

            }

        }

        while(m--){

            scanf("%d", &a);

            printf("%d\n", solve(a));

        }

    }

    return ;

}