给定一颗树，每个节点都有忠诚和能力两个参数，随意指定一个节点，要求在它的子树中找一个节点代替它，这个节点要满足能力值大于它，而且是忠诚度最高的那个。
首先，dfs一下，处理出L[i], R[i]表示dfs序，则R[i] - L[i] + 1 就是当前i这个节点拥有的子孙个数。
对于一颗树，dfs的时候，访问节点有先后顺序，那么可以用一个struct node List[maxn];表示这课树中访问的先后顺序。
例如这颗树，我假设是先访问0 --> 3 --> 2 ---> 4 ---> 5 ---> 1
这样我用一个List数组保存了，同时记录了L[i]和R[i]。那么对于每次询问删除一个节点cur，就是在[L[cur], R[cur]]里面选择了。例如节点2，L[2] = 2, R[2] = 4。那么就变成了区间最值问题。
分块：块内维护一个数组mx[i]表示当前这个块内能力值 > List[i].ablity的最大忠诚度。想要维护这个，就要开多个数组to_sort[]同样是记录dfs序，但是它要排序，按能力排序，这样可以O(magic)维护完成。
对于每个查询，不在块内的，暴力，在的，二分出一个 > 当前能力的pos，mx[pos]就是答案。
复杂度 O (nsqrt(n) + msqrt(n) * logn)
感觉数据略水，应该用线段树优化掉sqrt(n)
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 50000 + 20; struct edge { int u, v, next; } e[maxn * 2]; int first[maxn], R[maxn], L[maxn], mx[maxn]; int magic; struct node { int abliatly, loyalty ; bool operator < (const node &rhs) const { return abliatly < rhs.abliatly; } } a[maxn], List[maxn], to_sort[maxn]; int get_id[1000000 + 20]; int n, num; void add (int u, int v) { ++num; e[num].u = u; e[num].v = v; e[num].next = first[u]; first[u] = num; } bool book[maxn]; int index; void dfs (int cur) { L[cur] = index; for (int i = first[cur]; i; i = e[i].next) { if (book[e[i].v]) continue; book[e[i].v] = 1; ++index; List[index] = to_sort[index] = a[e[i].v]; dfs (e[i].v); } R[cur] = index; } int find (int begin, int end, int val) { int t = end; if (to_sort[end].abliatly < val) return -1; //不够它大 if (to_sort[begin].abliatly > val) return mx[begin];//bigger while (begin <= end) { int mid = (begin + end) >> 1; if (to_sort[mid].abliatly > val) end = mid - 1; else begin = mid + 1; } if (begin > t) return -1; return mx[begin]; } void work () { int Q; scanf ("%d%d", &n, &Q); magic = (int) sqrt (n * 1.0); for (int i = 1; i <= n - 1; ++i) { int fa, lo, ab; scanf ("%d%d%d", &fa, &lo, &ab); add (fa, i); a[i].abliatly = ab; a[i].loyalty = lo; get_id[lo] = i; } dfs (0); //dfs 构图 for (int i = 0; i < n; i += magic) { int j = i + magic; if (j > n) break; sort (to_sort + i, to_sort + j); mx[j - 1] = to_sort[j - 1].loyalty; for (int k = j - 2; k >= i; --k) { mx[k] = mx[k + 1] > to_sort[k].loyalty ? mx[k + 1] : to_sort[k].loyalty; } } while (Q--) { int id; scanf ("%d", &id); int val = a[id].abliatly; int ans = -inf; int begin = L[id], end = R[id]; for (int i = begin; i <= end;) { if (i % magic == 0 && i + magic - 1 <= end) { int t = find (i, i + magic - 1, val); ans = max (ans, t); i += magic; } else { if (List[i].abliatly > val && ans < List[i].loyalty) { ans = List[i].loyalty; } ++i; } } printf ("%d ", ans < 0 ? -1 : get_id[ans]); } return ; } int main () { #ifdef local freopen("data.txt","r",stdin); #endif int t; scanf ("%d", &t); a[0].abliatly = -1; a[0].loyalty = -1; List[0] = to_sort[0] = a[0]; while (t--) { work (); memset (first, 0, sizeof first); memset (book, 0, sizeof book); num = 0; index = 0; memset (mx, 0, sizeof mx); } return 0; }
线段树预处理优化：
同样是dfs序处理好，然后按能力从大到小排序，相同的，按id从小到大排序。因为id小的，必然不能成为后面的替身。
然后首先把线段树初始化为-1，按照能力从大到小去线段树L[id] --- R[id]中查找。
id就是那个cur，因为它的边是fa -- i的。//正因为这样，才能用这种方法
为什么呢？ 如果它建树的过程不是这样的话，就是不是一直往下建，（这样确保了id小的一定更高级）。这样就没法用id去比较它们的关系了。这个时候，只能分块做了。
然后就从大到小加入线段树，确保每次查找都是有效值即可
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 50000 + 20; struct edge { int u, v; int next; } e[maxn * 2]; struct node { int loyalty, ability, id; bool operator < (const node &rhs) const { if (ability != rhs.ability) return ability > rhs.ability; else return id < rhs.id; } } a[maxn]; int num; int first[maxn], L[maxn], R[maxn], get_id[1000000 + 20]; void add (int u, int v) { ++num; e[num].u = u; e[num].v = v; e[num].next = first[u]; first[u] = num; } bool book[maxn]; int index; void dfs (int cur) { L[cur] = index; for (int i = first[cur]; i; i = e[i].next) { if (book[e[i].v] == 0) { book[e[i].v] = 1; index++; dfs (e[i].v); } } R[cur] = index; } struct data { int L,R,mx; //每个节点，都记录一个区间[L,R]。还有记录区间总和 int mid() { return (L + R)/2; } } SegTree[maxn<<2]; //右移两位，就是*4 void built (int root,int begin,int end) { SegTree[root].L = begin; SegTree[root].R = end;//覆盖区间 if (begin == end) { SegTree[root].mx = -1; return ; } built(root<<1,begin,SegTree[root].mid()); built(root<<1|1,SegTree[root].mid()+1,end); SegTree[root].mx = max(SegTree[root<<1].mx,SegTree[root<<1|1].mx); return ; } void addTT (int root,int pos,int val) { if (SegTree[root].L == pos && pos == SegTree[root].R) { SegTree[root].mx = val; return ; } if (pos <= SegTree[root].mid()) addTT(root<<1,pos,val); else if (pos >= SegTree[root].mid()+1) addTT(root<<1|1,pos,val); SegTree[root].mx = max (SegTree[root<<1].mx,SegTree[root<<1|1].mx); return ; } //[begin,end]是要查询的区间，如果所求区间包含线段树覆盖区间，就可以返回 int find (int root,int begin,int end) //区间查询 { //查询[1,7]的话，左子树区间覆盖了[1,6]，也可以直接返回,左子树最大值嘛 if (begin <= SegTree[root].L && end >= SegTree[root].R) return SegTree[root].mx; //覆盖了 if (end <= SegTree[root].mid()) //完全在左子数 return find(root<<1,begin,end); else if (begin >= SegTree[root].mid() + 1) //完全在右子树 return find(root<<1|1,begin,end); else { int Lmax = find(root<<1,begin,end); int Rmax = find(root<<1|1,begin,end); return max(Lmax,Rmax); } } int ans[maxn]; void work () { int n, Q; scanf ("%d%d", &n, &Q); for (int i = 1; i <= n - 1; ++i) { int fa, lo, ab; scanf ("%d%d%d", &fa, &lo, &ab); add (fa, i); a[i].loyalty = lo; a[i].ability = ab; a[i].id = i; get_id[lo] = i; } dfs (0); // for (int i = 0; i < n; ++i) { // printf ("%d %d ", L[i], R[i]); // } built (1, 1, n - 1); //全部设置为-1先 sort (a + 1, a + n); // for (int i = 1; i <= n - 1; ++i) { // printf ("%d %d ", a[i].ability, a[i].loyalty); // } for (int i = 1; i <= n - 1; ++i) { int id = get_id[a[i].loyalty]; //printf ("%d**** ", id); // printf ("%d %d ", L[id], R[id]); int t = find (1, L[id], R[id]); //ans[id] = t; if (t == -1) { ans[id] = -1; } else { ans[id] = get_id[t]; } addTT (1, L[id], a[i].loyalty); } for (int i = 1; i <= Q; ++i) { int id; scanf ("%d", &id); printf ("%d ", ans[id]); } return ; } int main () { #ifdef local freopen("data.txt","r",stdin); #endif int t; scanf ("%d", &t); while (t--) { index = 0; work (); memset (book, 0, sizeof book); memset (first, 0, sizeof first); index = 0; num = 0; } return 0; }