题意：
给你 n个点。他们有 上下级关系，一个点只有一个上级，一个上级 可以有多个下级，每个点有两个属性，能力值 、忠诚度（每个节点的忠诚度不同），求我们要删除 一个节点， 则我们 需从 其下级中选出 一个节点，其能力值 比该节点 要高，且 忠诚度是（比其能力高的下级节点中的）最高
题解：
首先将树状结构，转化为 线状结构，
可以遍历一遍将树上每个点标记为一维区间上的某个点，且在同一棵子树内的点是连续的一段。
然后，将所有点按能力从大到小排序，能力相同的编号小的排在前面，然后扫描一遍，扫描时维护一颗线段树，
（我们先插入线段树的是，比其能力值 大的，我们只要从这些里面找到，忠诚度最高的就 可以了）
先查找该点为根节点的子树内的最优值，然后插入该点的忠诚度。
1 #include<stdio.h> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include< set> 8 #include<map> 9 #define Min(a,b) a>b?b:a 10 #define Max(a,b) a>b?a:b 11 #define CL(a,num) memset(a,num,sizeof(a)); 12 #define inf 9999999 13 #define maxn 100110 14 #define mod 100000007 15 #define eps 1e-6 16 #define ll long long 17 #define M 15520 18 using namespace std; 19 map< int, int>map1; 20 vector< int>g[maxn] ; 21 int num ,ans[maxn],n,m,l[maxn],r[maxn]; 22 struct staff 23 { 24 int loy; 25 int abt; 26 int id; 27 }sta[maxn]; 28 struct node 29 { 30 int l; 31 int r; 32 int mx; 33 }p[maxn * 2]; 34 bool cmp (staff a, staff b) 35 { 36 return a.abt > b.abt ; 37 } 38 void dfs( int x) // 编号变为线状结构 39 { 40 41 l[x] = num++; 42 for( int i = 0; i < g[x].size(); ++i) 43 { 44 dfs(g[x][i]); 45 } 46 47 r[x] = num ; 48 49 } 50 void build( int x, int l, int r) 51 { 52 p[x].l = l; 53 p[x].r = r; 54 p[x].mx = - 1 ; 55 if(l == r) return ; 56 int mid = (l + r) / 2; 57 build(x* 2,l,mid); 58 build(x* 2+ 1,mid + 1,r); 59 60 } 61 int get( int x, int l, int r) 62 { 63 64 if( r < l ) return - 1 ; 65 if(p[x].l == l && p[x].r == r) 66 { 67 68 return p[x].mx; 69 } 70 int mid = (p[x].l + p[x].r) / 2 ; 71 if(r <= mid) return get(x * 2,l,r); 72 else 73 { 74 if(l > mid) return get(x * 2 + 1,l,r); 75 else 76 { 77 return max( get(x * 2,l,mid), get(x * 2 + 1,mid + 1,r)); 78 } 79 } 80 } 81 void insert( int x, int pos, int d) 82 { 83 if(p[x].l == p[x].r ) 84 { 85 p[x].mx = d; 86 return ; 87 88 } 89 int mid = (p[x].l + p[x].r) / 2 ; 90 if(pos <= mid) insert(x* 2,pos,d); 91 else 92 { 93 insert(x* 2 + 1, pos,d); 94 95 } 96 97 p[x].mx = max(p[x* 2].mx,p[x* 2+ 1].mx); 98 99 } 100 void init() 101 { 102 for( int i = 0; i <= n;++i ) 103 g[i].clear(); 104 105 map1.clear(); 106 107 num = 0 ; 108 } 109 int main() 110 { 111 int t,u,loy,abt,a,j,i; 112 scanf( " %d ",&t); 113 while(t--) 114 { 115 scanf( " %d%d ",&n,&m); 116 init(); 117 118 for( i = 1 ; i < n;++i) 119 { 120 scanf( " %d%d%d ",&u,&loy,&abt); 121 g[u].push_back(i); 122 sta[i].loy = loy; 123 sta[i].abt = abt ; 124 sta[i].id = i; 125 map1[loy] = i; 126 127 } 128 129 dfs( 0); 130 131 build( 1, 0,num - 1); 132 sort(sta + 1,sta + n,cmp); // 排序为了下面 查询 打基础，排好序之后，我们插入时，保证了，比 i 大的已经插入了这时直接找，忠诚的uida就可以了 133 134 135 for( i = 1 ; i < n ;i = j) 136 { 137 j = i; 138 139 while(j < n &&sta[i].abt == sta[j].abt) 140 { 141 int id = sta[j].id ; 142 loy = get( 1,l[id] + 1,r[id] - 1); 143 144 if(loy != - 1) ans[id] = map1[loy] ; 145 else ans[id] = - 1; 146 147 ++j; 148 149 } 150 151 j = i ; 152 while(j < n && sta[i].abt == sta[j].abt ) 153 { 154 int id = sta[j].id; 155 insert( 1,l[id],sta[j].loy); 156 ++j; 157 } 158 159 160 161 } 162 while(m--) 163 { 164 scanf( " %d ",&a); 165 166 printf( " %d\n ",ans[a]) ; 167 } 168 } 169 170 }