[原创]HDU 4366 Successor [树形转线形+线段树]【数据结构+技巧】

2017-03-03 16:05:08 Tabris_ 阅读数：265

博客爬取于2020-06-14 22:41:30
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/60141601

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4366
---------------------------------------------------------------------------------------------------------------.

Successor

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 4173 Accepted Submission(s): 1032

Problem Description
Sean owns a company and he is the BOSS.The other Staff has one Superior.every staff has a loyalty and ability.Some times Sean will fire one staff.Then one of the fired man’s Subordinates will replace him whose ability is higher than him and has the highest loyalty for company.Sean want to know who will replace the fired man.

Input
In the first line a number T indicate the number of test cases. Then for each case the first line contain 2 numbers n,m (2<=n,m<=50000),indicate the company has n person include Sean ,m is the times of Sean’s query.Staffs are numbered from 1 to n-1,Sean’s number is 0.Follow n-1 lines,the i-th(1<=i<=n-1) line contains 3 integers a,b,c(0<=a<=n-1,0<=b,c<=1000000),indicate the i-th staff’s superior Serial number,i-th staff’s loyalty and ability.Every staff ‘s Serial number is bigger than his superior,Each staff has different loyalty.then follows m lines of queries.Each line only a number indicate the Serial number of whom should be fired.

Output
For every query print a number:the Serial number of whom would replace the losing job man,If there has no one to replace him,print -1.

Sample Input
1
3 2
0 100 99
1 101 100
1
2

Sample Output
2
-1

Author
FZU

Source
2012 Multi-University Training Contest 7

----------------------------------------------------------------------------------------------------------------.
题目大意：
给一个公司的上下级关系图，每个员工有一个上级，一个忠诚度，一个能力值，
现在老板（0），要开除一个员工，然后在这个员工的直接或间接能力值大于这个员工下级中找忠诚度最大的人来代替这个员工，如果有输出代替的员工的编号，没有输出-1

解题思路:

首先，要明白如何将一个数形转化为线形

其实就是从根节点进行搜索，
然后向下dfs遍历树，依次进行编号，
同时能保证子树的编号一定大于父节点的编号，

同时借用两个数组，$L[_],R[_]分别表示这个节点分别表示这个节点u的子树的节点编号在的子树的节点编号在\big(L[u],R[u]\big),开区间$ 内。

这样在进行对子树 进行的操作的时候 可以借助数据结构 对区间进行查找，

然后将员工按能力值排序，

依次将一个个员工插入到线段树中，单点更新即可，
找这个员工下属忠诚度的最大的，直接区间查询就行了，
因为我们已经将树形转化成了线形，所以能够确保结果的正确性

然后注意下代码细节就好了。

操他妈的 两处笔误,卡了2个小时
1 sort (+1,+n +1)
2 j打成i
怎么这么菜！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

附本题代码
----------------------------------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
# include <bits/stdc++.h>

using namespace std;

# define pb         push_back

const int    N   = 50000+7;
/***********************************************************************/

struct Node{
    int l,r;
    int val;
    int len(){return (r-l+1);}
    int md(){return (r+l)>>1;}
}tree[N<<2];
# define ll  (rt<<1)
# define rr  (rt<<1|1)
# define mid (tree[rt].md())

void pushup(int rt){
    tree[rt].val = max(tree[ll].val,tree[rr].val);
}

void build(int rt,int l,int r){
    tree[rt].l=l,tree[rt].r=r;
    tree[rt].val=-1;
    if(l==r)return ;
    build(ll,l,mid);
    build(rr,mid+1,r);
    return ;
}

void update(int rt,int pos,int val){
    if(tree[rt].l==tree[rt].r){
        tree[rt].val = val;
        return ;
    }
    if(pos<=mid) update(ll,pos,val);
    else         update(rr,pos,val);
    pushup(rt);
}

int query(int rt,int L,int R){
    if(L>R) return -1;
    if(L<=tree[rt].l&&tree[rt].r<=R){
        return tree[rt].val;
    }
    int ans = -1;
    if(L<=mid) ans = max(ans,query(ll,L,R));
    if(R> mid) ans = max(ans,query(rr,L,R));
    return ans;
}

/***********以上是 segment tree**************/

struct node {
    int Superior,loyalty ,ability;
    int id;
}p[N];
int L[N],R[N],ans[N];
vector <int >G[N];
map<int ,int >mmp;

bool cmp(node a,node b){
    return a.ability>b.ability;
}

int cnt ;
void dfs(int u){
    L[u]=cnt++;
    int sz=G[u].size();
    for(int i=0;i<sz;i++){
        int v=G[u][i];
        dfs(v);
    }
    R[u]=cnt;
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++)G[i].clear();mmp.clear();
        for(int i=1;i<n;i++){
            scanf("%d %d %d",&p[i].Superior,&p[i].loyalty,&p[i].ability);
            p[i].id=i;
            G[p[i].Superior].pb(i);
            mmp[p[i].loyalty]=i;
        }

        sort(p+1,p+n,cmp);
        cnt=0,dfs(0);
        build(1,0,cnt-1);

        memset(ans,-1,sizeof(ans));

        for(int i=1,j,id,res;i<n;i=j){
            for(j=i;j<n&&p[i].ability==p[j].ability;){
                id = p[j++].id;
                res = query(1,L[id]+1,R[id]-1);
                ans[id] = (res==-1)?-1:mmp[res];
            }
            for(j=i;j<n&&p[i].ability==p[j].ability;){
                id = p[j].id;
                update(1,L[id],p[j++].loyalty);
            }
        }

        int x;
        while(m--){
            scanf("%d",&x);
            printf("%d\n",ans[x]);
        }
    }
    return 0;
}