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

Successor

1
3 2
0 100 99
1 101 100
1
2

2
-1

题意：（转）

某公司有 n 个人，编号从 0 到 n-1 ，0号是BOSS。除BOSS外，每个人有忠诚度和能力两个属性，每个人的忠诚度都不同。每个人都有可能被BOSS炒鱿鱼，当某个人被炒后，他的所有下级中能力大于他且具有最大忠诚度的人将取代他的位置。现在给定所有人的上下级关系（下级的编号总是比上级大）和一些被炒鱿鱼的人的编号，输出取代被炒人的人的编号，如果没人取代被炒人，输出“-1”。

PS：首先，把以每个节点为根的子树转化为连续区间以便于处理。然后，按能力值由大到小对员工进行排序，能力值相同时，编号小的排在前面。最后，从左到右求以某个人为根的子树中忠诚度最大的人的编号，然后将根的忠诚度插入到线段树中。

因为每个忠诚值必然对应一个唯一的序号，那么开个 map映射一下好了。

DFS时间戳，记录进入结点的时间戳和出结点的时间戳，两个时间戳之间的都是这个结点的子孙结点了。

#pragma comment(linker,"/STACK:102400000,102400000")  //手动扩栈
#include <cstdio>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
#define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1

const int maxn = 50017;
int n, m;
int Max[maxn << 2], ans[maxn];
int L[maxn], R[maxn], idx;
int vis[maxn];
map<int, int> mm;
vector<int> v[maxn];

struct Staff
{
    int b, c;
    int id;
} s[maxn];

bool cmp(Staff s1, Staff s2)
{
    if(s1.c == s2.c)
    {
        return s1.id < s2.id;
    }
    return s1.c > s2.c;
}

void PushUP(int rt) //把当前结点的信息更新到父结点
{
    Max[rt] = max(Max[rt<<1],Max[rt<<1|1]);
}

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

void update(int p, int c, int l, int r, int rt)
{
    if(l == r)
    {
        Max[rt] = c;
        return ;
    }
    int mid = (l + r) >> 1;
    if(p <= mid)
    {
        update(p , c , lson);
    }
    else
    {
        update(p , c , rson);
    }
    PushUP(rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R)
    {
        return Max[rt];
    }
    int mid = (l + r) >> 1;
    int ret = -999;
    if(L <= mid)
    {
        ret = max(ret, query(L , R , lson));
    }
    if(R > mid)
    {
        ret = max(ret, query(L , R , rson));
    }
    return ret;
}

void dfs(int x)
{
    L[x] = idx;
    vis[x] = 1;
    int num = v[x].size();
    for(int i = 0; i < num; i++)
    {
        if(!vis[v[x][i]])
        {
            idx++;
            int tt = v[x][i];
            dfs(tt);
        }
    }
    R[x] = idx;
}

void init()
{
    memset(vis, 0, sizeof(vis));
    for(int i = 0; i < maxn; i++)
    {
        v[i].clear();
    }
    mm.clear();
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n, &m);
        int a, b, c;
        for(int i = 1; i <= n-1; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            v[a].push_back(i);
            s[i].b = b;
            s[i].c = c;
            s[i].id = i;
            mm[b] = i;
        }
        mm[-1] = -1;
        sort(s+1, s+n, cmp);//从大到小
        build(1, n-1, 1);
        idx = 0;
        
        //DFS时间戳，记录进入结点的时间戳和出结点的时间戳，
        //两个时间戳之间的都是这个结点的子孙结点了
        dfs(0);

        for(int i = 1; i <= n-1; i++)
        {
            int ret = query(L[s[i].id], R[s[i].id], 1, n-1, 1);
            ans[s[i].id] = mm[ret];
            update(L[s[i].id], s[i].b, 1, n-1, 1);
        }
        int k;
        for(int i = 0; i < m; i++)
        {
            scanf("%d",&k);
            printf("%d\n",ans[k]);
        }
    }
    return 0;
}
/*
9
5 3
0 100 99
1 80 100
1 102 150
3 90 50
1
2
3

5 3
0 100 99
1 80 100
2 102 150
3 90 50
1
2
3
*/

HDU 4366 Successor（线段树 DFS时间戳啊）

原文：http://blog.csdn.net/u012860063/article/details/47299231