本文共 2507 字，大约阅读时间需要 8 分钟。
首先说明这题不是在线算法，也不能说是离线算法，就是一个预处理能够把所有的结果全部算出来再O(1)的时间得到答案。
首先我们要将一这种上下属的关系通过一个dfs转化为一维的关系，相同属性（指为同一个人的下属）的话，那么在物理上就是连续的。
这样处理后，我们考虑一个员工能够被替代的话，那么替代他的人的能力值就一定是比他高的，因此我们按照能力值对所有的人进行一次排序，能力值相同的就按照标号从小到大排，这样的话，就能够保证每次询问一个点时，线段树中的所有值都是满足上下属关系的。排好序后，再从左到右扫描一遍，每次先查询如果解雇这个员工，谁将成为他的最佳替代者。
代码如下：
#include #include #include #include #include using namespace std;int N, Q, idx, head[50005], L[50005], R[50005];int mp[50005], NO, ret[50005];map MP;struct Edge{ int v, lay, abi, next;}e[50005];struct Node{ int l, r, mlay; // mlay 代表区间内最高的忠诚度}s[50005 * 4];struct People{ int lay, abi, NO; bool operator < (People temp) const { if (abi != temp.abi) return abi > temp.abi; return NO < temp.NO; }}po[50005];void AddEdge(int x, int v, int lay, int abi){ ++idx; e[idx].v = v, e[idx].lay = lay; e[idx].abi = abi, e[idx].next = head[x]; head[x] = idx;}void dfs(int p){ mp[p] = NO; L[p] = NO; for (int i = head[p]; i != -1; i = e[i].next) { ++NO; dfs(e[i].v); } R[p] = NO;}void build(int p, int l, int r){ s[p].l = l, s[p].r = r, s[p].mlay = -1; if (l != r) { int mid = (l + r) >> 1; build(p<<1, l, mid); build(p<<1|1, mid+1, r); }}void push_up(int p){ s[p].mlay = max(s[p<<1].mlay, s[p<<1|1].mlay);}void modify(int p, int pos, int info){ if (s[p].l == s[p].r) { s[p].mlay = po[info].lay; return; } int mid = s[p].l + s[p].r >> 1; if (pos <= mid) { modify(p<<1, pos, info); } else { modify(p<<1|1, pos, info); } push_up(p);}int query(int p, int l, int r){ if (s[p].l == l && r == s[p].r) { return s[p].mlay; } int mid = s[p].l + s[p].r >> 1; if (r <= mid) { return query(p<<1, l, r); } else if (l > mid) { return query(p<<1|1, l, r); } else { return max(query(p<<1, l, mid), query(p<<1|1, mid+1, r)); }}int main(){ int T, x, lay, abi, c; scanf("%d", &T); while (T--) { NO = 0; idx = -1; MP.clear(); memset(head, 0xff, sizeof (head)); scanf("%d %d", &N, &Q); for (int i = 1; i < N; ++i) { scanf("%d %d %d", &x, &lay, &abi); po[i].NO = i, po[i].lay = lay, po[i].abi = abi; MP[lay] = i; // 唯一标记好这个忠诚度属于哪个人 AddEdge(x, i, lay, abi); } dfs(0); build(1, 0, NO); sort(po+1, po+N); // 共有N-1条信息 for (int i = 1; i < N; ++i) { ret[po[i].NO] = query(1, L[po[i].NO], R[po[i].NO]); if (ret[po[i].NO] != -1) { ret[po[i].NO] = MP[ ret[po[i].NO] ]; } modify(1, mp[po[i].NO], i); // mp[p[i].NO] 传入线段树内编号，i传入数据源 } while (Q--) { scanf("%d", &c); printf("%d\n", ret[c]); } } return 0;}
转载于:https://www.cnblogs.com/Lyush/archive/2012/08/15/2640910.html