HDU 4366 Successor( DFS序+ 线段树 )

Successor

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

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

 

 　　题目的意思是给出一棵树， 然后树上每个节点有能力值，忠诚值。给出m个询问，要你找出某个结点后代中，忠诚值最高且能力值比它大的。

　　一开始思路不难想出要 ， 按照能力值从大到小，编号从小到大排完再插入（ 因为题目给出编号小的是上司 ，所以要先插入 ，因为如果下属先插入

的话 ，如果它属于同它能力值相同的上司的后代，他有可能影响了它上司的更新，没有符合能力值严格大于的条件 ）。然后取出忠诚值最大的话就用一颗

线段树处理就OK了。关键是怎么保证取的范围是属于这个节点的后代呢， 我就是卡了这个 ，其实，处理完DFS序以后，那个区间正正是该节点的后代了。

最后单点更新该点到DFS序的起始点中就可以了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <algorithm>

using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 500011 ;
const int inf = 1e9+7;

#define X first
#define Y second
#define root 1,n,1
#define lr rt<<1
#define rr rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1

int n,m;

struct node{
    int id,b,c;
    bool operator<(const node &a)const{
        if( c != a.c )return c>a.c;
        else return id < a.id ;
    }
}e[N];

int pos1[N] , pos2[N] , dfs_clock , ans[N] , F[N];

vector<int>g[N];

void Init() {
    for( int i = 0 ; i < N ; ++i ) g[i].clear();
}
void dfs( int u ) {
    pos1[u] = pos2[u] = ++dfs_clock;
    for( int i = 0 ; i < g[u].size() ; ++i ) {
        int v = g[u][i];
        dfs(v); pos2[u] = pos2[v];
    }
}

int date[N<<2] ;

void Up( int rt ) {
    if( date[rr] == -1 || ( F[ date[lr] ] >= F[ date[rr] ] ) ) date[rt] = date[lr] ;
    else date[rt] = date[rr];
}

void Build( int l , int r , int rt ) {
    date[rt] = -1 ;
    if( l == r ) return ;
    int mid = (l+r)>>1;
    Build(lson) , Build(rson) ;
}

void Update( int l , int r , int rt , int x ,int id ) {
    if( l == r ) {
        date[rt] = id ; return ;
    }
    int mid = (l+r)>>1;
    if( x <= mid ) Update(lson,x,id);
    else Update(rson,x,id);
    Up(rt);
}

int Query( int l , int r , int rt , int L , int R ) {
    if( l == L && r == R ) {
        return date[rt];
    }
    int mid = (l+r)>>1;
    if( R <= mid ) return Query(lson,L,R);
    else if( L > mid ) return Query(rson,L,R);
    else {
        int id1 = Query(lson,L,mid) , id2 = Query( rson,mid+1,R ) ;
        if( id2 == -1 || ( F[id1] >= F[id2] ) ) return id1 ;
        else return id2 ;
    }
}

void Solve() {
    dfs_clock = 0 ; dfs(0);
    Build(root);
    sort( e , e + n ) ;
    for( int i = 0 ; i < n ; ++i ) {
        int id = e[i].id ;
        ans[id] = Query(root,pos1[id],pos2[id]);
        Update(root,pos1[id],id );
    }
}

void Read() {
    scanf("%d%d",&n,&m);
    e[0].id = 0 , e[0].c = e[0].b = inf , F[0] = inf ;
    for( int i = 1 ; i < n ; ++i ) {
        int fa ;scanf("%d%d%d",&fa,&e[i].b,&e[i].c);
        e[i].id = i ; F[i] = e[i].b ;
        g[fa].push_back(i);
    }
}

void Output() {
    while( m-- ) {
        int x ;scanf("%d",&x);
        printf("%d
",ans[x]);
    }
}
int main(){
    #ifdef LOCAL
        freopen("in.txt","r",stdin);
    #endif // LOCAL
    ios::sync_with_stdio(false);
    int _ ; scanf("%d",&_);
    while(_--) Init() , Read() , Solve() , Output() ;
}