2015
05-23

# Successor

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.

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.

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.

1
3 2
0 100 99
1 101 100
1
2

2
-1

/*

（我们先插入线段树的是，比其能力值 大的，我们只要从这些里面找到，忠诚度最高的就 可以了）

*/
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn    100110
#define mod 100000007
#define eps  1e-6;
#define ll  long long
#define M   15520
using namespace std;
map<int,int>map1;
vector<int>g[maxn] ;
int num ,ans[maxn],n,m,l[maxn],r[maxn];
struct staff
{
int loy;
int abt;
int id;
}sta[maxn];
struct node
{
int l;
int r;
int mx;
}p[maxn * 2];
bool cmp (staff a, staff b)
{
return a.abt > b.abt ;
}
void dfs(int x)//编号变为线状结构
{
l[x] = num++;
for(int i = 0; i < g[x].size(); ++i)
{
dfs(g[x][i]);
}
r[x] = num ;
}
void build(int x,int l,int r)
{
p[x].l = l;
p[x].r = r;
p[x].mx = -1 ;
if(l == r) return  ;
int mid = (l + r) /2;
build(x*2,l,mid);
build(x*2+1,mid + 1,r);
}
int get(int x,int l,int r)
{
if( r < l ) return  -1 ;
if(p[x].l == l && p[x].r == r)
{
return p[x].mx;
}
int mid = (p[x].l + p[x].r) /2 ;
if(r <= mid)  return get(x * 2,l,r);
else
{
if(l > mid) return get(x * 2 + 1,l,r);
else
{
return max(get(x * 2,l,mid),get(x * 2 + 1,mid + 1,r));
}
}
}
void insert(int x,int pos,int d)
{
if(p[x].l == p[x].r )
{
p[x].mx = d;
return ;
}
int mid = (p[x].l + p[x].r) /2 ;
if(pos <= mid) insert(x*2,pos,d);
else
{
insert(x*2 + 1, pos,d);
}
p[x].mx = max(p[x*2].mx,p[x*2+1].mx);
}
void init()
{
for( int i = 0; i <= n; ++i )
g[i].clear();
map1.clear();
num = 0 ;
}
int main()
{
int t,u,loy,abt,a,j,i;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for( i = 1 ; i < n; ++i)
{
scanf("%d%d%d",&u,&loy,&abt);
g[u].push_back(i);
sta[i].loy = loy;
sta[i].abt = abt ;
sta[i].id = i;
map1[loy] = i;
}
dfs(0);
build(1,0,num - 1);
sort(sta + 1,sta + n,cmp);//排序为了下面 查询 打基础，排好序之后，我们插入时，保证了，比 i 大的已经插入了这时直接找，忠诚的uida就可以了
for( i = 1 ; i < n ; i = j)
{
j = i;
while(j < n &&sta[i].abt == sta[j].abt)
{
int id = sta[j].id ;
loy = get(1,l[id] + 1,r[id] - 1);

if(loy != -1) ans[id] = map1[loy] ;
else ans[id] = -1;
++j;
}
j = i ;
while(j < n && sta[i].abt == sta[j].abt )
{
int id =  sta[j].id;
insert(1,l[id],sta[j].loy);
++j;
}
}
while(m--)
{
scanf("%d",&a);
printf("%d\n",ans[a]) ;
}
}
return 0;
}


1. 不做的更好，难道我们要向第三世界看齐？这是工作态度的问题，就是真正有意义的事情，就从这一点工作细节上和官方，媒体的言论就能看出国人处处皆不认真，中国就是缺乏较真的人，大家都和稀泥，不分是非，关键的就是差在这。建议你看看胡适写的《差不多先生传》。