Successor
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
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
//題意：總共有n個人（0—n-1），其中編号為0的是老闆，1—n-1是員工，每個員工有3個參數，他上司的編号，忠誠度和能力值，每個人隻有1個上司，每個人的忠誠度唯一，且每個人的編号肯定比他的上司大。現在老闆要開除員工，并且要在這個被開除的人的下屬或他下屬的下屬裡去找一個人，要求能力值比這個被開除的人大（不能等于），并且忠誠度要在滿足以上要求的人中最大，來頂替那個被開除的人。
PS：如果找到了這個人輸出後，不用真的線上段樹中把這個人去跟那個被開除的人交換，題目意思是如果這個人被開除了誰去頂替，是如果！...
//思路：
1.首先，要确定所有員工之間的上下級關系，我們先用c++裡的vector容器來存每個人的下屬（這裡的 vector容器其實就是一個二維數組，但不能用二維數組，因為他大小要map[50000][50000]，會爆棧的...），然後用一個DFS，記錄遞歸的時候每個人DFS進去的時間和DFS結束的時間，這樣每個人就有了一個區間，而且一個人的下屬和他下屬的下屬的區間必然是他區間的一個子集。
2.第一步完成之後，我們先建線段樹，線段樹裡一個節點包含2個值id和max_loyality，表示這個線段樹這個節點區間裡忠誠度的最大值和那個人的節點id，一開始建樹的時候把這些都先設定成-1好了。
3.再把所有員工按能力值從大到小排個序，然後依次去update線段樹，這題線段樹是單點更新的，更新的時候節點的位置是第一步DFS确定的區間的左端點，即進DFS的時間，因為這個時間每個人必然是不同的，根據這個去确定這個人線上段樹中的位置。然後向上Pushup的時候，父親節點的值是左右孩子中忠誠度的最大值和那個節點的id。
4.因為我們是按能力值從大到小去update的，我們隻要在插入那個點之前去尋找那個線段樹中滿足要求替換他的人就行了，因為替換者的能力值是一定要比他大的。查詢的時候，要輸入要查的那個人DFS确定的區間（來确定是不是被删的那個人的下屬或下屬的下屬）。query求出的是滿足要求的最大忠誠度，因為題目說每個人的忠誠度是唯一的，即一個忠誠度隻對應1個人，我們可以通過一個hash[]，用忠誠度來映射這個人的id，注意忠誠度最大是有 1000000的，是以hash數組也要開這麼大。
具體實作看代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
const int MAX = 50000 + 100;
const int MAXN = 1000000 + 100;
typedef struct {
int id; //id
int superior; //上司id
int loyalty; //忠誠度
int ability; //能力值
}Staff;
typedef struct {
int loy; //最大的忠誠度的值
int id; //忠誠度最大的這個人的id
}Tree;
typedef struct {
int s, e;//分别表示dfs進去的時間和出來的時間
}Node;
Tree tree[MAX * 4]; //線段樹數組
Staff staff[MAX]; //員工的資訊
Node area[MAX]; //每個員工dfs的區間
vector<int> edge[MAX]; //儲存每個人他所有下屬的id
int ans[MAX]; //用來儲存如果炒掉這個人之後來頂替他的那個人的id
int ha[MAXN]; //通過忠誠度來映射一個人的id（因為每個人忠誠度唯一）
int dfstime;
bool cmp(Staff a, Staff b)
{
//按能力值從大到小排序
return a.ability > b.ability;
}
void dfs(int x)
{
area[x].s = dfstime++;
for (int i = 0; i < edge[x].size(); i++)
{
dfs(edge[x][i]);
}
area[x].e = dfstime;
}
void Pushup(int root)
{
//兩個節點的父親節點是他們中忠誠度最大的那個
if (tree[root << 1].loy > tree[root << 1 | 1].loy)
{
tree[root].loy = tree[root << 1].loy;
tree[root].id = tree[root << 1].id;
}
else
{
tree[root].loy = tree[root << 1 | 1].loy;
tree[root].id = tree[root << 1 | 1].id;
}
}
void build(int root, int l, int r)
{
//一開始都先設定成-1
//後面會逐個單點更新
tree[root].id = tree[root].loy = -1;
if (l == r)
return;
int mid = (l + r) / 2;
build(root << 1, l, mid);
build(root << 1 | 1, mid + 1, r);
}
//線段樹中我們用dfs進去的那個時間來确定節點線上段樹的位置
//因為dfs進去的那個時間必然唯一
//單點更新
void update(int root, int l, int r, int pos, int id, int val)
{
if (l == r)
{
tree[root].id = id;
tree[root].loy = val;
return;
}
int mid = (l + r) / 2;
if (pos <= mid)
update(root << 1, l, mid, pos, id, val);
else
update(root << 1 | 1, mid + 1, r, pos, id, val);
Pushup(root);
}
//找符合條件的最大忠誠度
int query(int root, int l, int r, int L, int R)
{
if (L > R)
return -1;
if (L <= l&&r <= R)
return tree[root].loy;
int mid = (l + r) / 2;
int ret = -1;
if (L <= mid)
ret = max(ret, query(root << 1, l, mid, L, R));
if (R > mid)
ret = max(ret, query(root << 1 | 1, mid + 1, r, L, R));
return ret;
}
int main()
{
int T;
int n, m;
scanf("%d", &T);
while (T--)
{
int a;
scanf("%d%d", &n, &m);
memset(ha, 0, sizeof(ha));
for (int i = 0; i <= n; i++)
edge[i].clear();
for (int i = 1; i <= n - 1; i++)
{
scanf("%d%d%d", &staff[i].superior, &staff[i].loyalty, &staff[i].ability);
edge[staff[i].superior].push_back(i);
staff[i].id = i;
ha[staff[i].loyalty] = i;
}
sort(staff + 1, staff + n, cmp);
dfstime = 0;
dfs(0);
build(1, 0, dfstime - 1);
memset(ans, -1, sizeof(ans));
/*
按能力從大到小去插入，這樣每次查詢查的人都是能力比他大的，
這樣我們隻要去找符合條件的最大忠誠度就可以了。
怎麼樣算符合條件：
是這個人的下屬或者下屬的下屬，隻要滿足去替換的那個人的dfs
進出區間包含在這個人區間裡就行了。
*/
for (int i = 1, j; i < n; i = j)
{
j = i;
//逐個查詢能力值相同的人
//因為頂替他的人的能力一定要比他強，不能相同
while (j < n&&staff[j].ability == staff[i].ability)
{
int id = staff[j].id;
int loy = query(1, 0, dfstime - 1, area[id].s + 1, area[id].e - 1);
ans[id] = (loy == -1 ? -1 : ha[loy]);
j++;
}
j = i;
//逐個update能力值相同的人的資訊
while (j < n&&staff[j].ability == staff[i].ability)
{
int id = staff[j].id;
update(1, 0, dfstime - 1, area[id].s, id, staff[j].loyalty);
j++;
}
}
for (int i = 0; i < m; i++)
{
scanf("%d", &a);
printf("%d\n", ans[a]);
}
}
return 0;
}
![第一次CSP模測第一題第二題第三題[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)