继任者
时限：1s内存：32M
★问题描述:
S开了家公司，他自己是老板，其余员工都有一名直系上级，每名员工都有对公司的忠诚度和能力值。S时不时会开除某名员工，由其下属中能力值大于这名员工的人中忠诚度最高的担任其职务。他想知道，若开除某名员工，该选谁担任其职务。A是B的下属是指，A的直系上级是B或B的下属。
★数据输入：
第一行输入T表示CASE数。接下来T组数据，每组数据第一行输入两个整数n,m(2<=n，m<=25000)，表示有该公司包括S有n个人，有m组询问。员工按输入顺序从1到n-1编号，S编号为0。接下去1到n-1行，每行三个整数a,b,c(0<=a<=n-1,0<=b,c<=1000000)分别表示第i名员工的直系上级编号、忠诚度、能力值，每名员工的编号大于其上级的编号，且他们的忠诚度各不相同。接下去m行，每行一个整数q(1<=q<=n-1)表示询问若开除第q名员工应该选谁担任其职务。注意询问并没有真正开除员工，也就是说各个询问假设要开除的员工互不影响。
★结果输出:
对于每个询问输出一个数表示该选的员工的编号，若这样的员工不存在则输出-1。
|
输入示例 |
输出示例 |
|
1 3 2 0 100 99 1 101 100 1 2 |
2 -1 |
本来是按B值对结点从大到小排序-然后按顺序插入线段树
因为插入前结点所对应的区间一定只有比父节点B值大的，因此直接输出A值最大的即可（线段树）
实际做法：暴力插入结点，直到找到根或找到比它A,B值都大（这样上司选它一定更优）的为止。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (25000+10)
#define MAXCi (1000000)
int n,m;
struct node
{
int key,fim,fa,ans;
node():ans(-1){}
node(int _key,int _fim,int _fa):key(_key),fim(_fim),fa(_fa),ans(-1){}
}a[MAXN];
void update(int x)
{
for (int now=a[x].fa;now;now=a[now].fa)
{
if (a[x].key>a[now].key&&(a[now].ans==-1||a[a[now].ans].fim<a[x].fim)) a[now].ans=x;
else if (a[x].key<a[now].key&&a[x].fim<a[now].fim) break;
}
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n-1;i++)
{
cin>>a[i].fa>>a[i].fim>>a[i].key;update(i);
}
for (int i=1;i<=m;i++)
{
int p;
cin>>p;
cout<<a[p].ans<<endl;
}
return 0;
}