HDU 4366 Successor

题意：给你一棵树，求树中某节点子树中能力值大于它且忠诚度最高的那个。

在第一次看到这个问题是，我有一个疑问：

解决这个问题有两个关键点：

1.树形结构到线性结构的转换

原因：员工关系整棵树是一棵结构不确定的树，员工编号不一定连续，对于查询其符合条件的下属有很大困难（只能暴力）。而编号之后可以将子树映射到编号连续的一段区间，这时就可以用线段树快速查询最值。
做法：用邻接表保存树，从根开始DFS，记录每棵子树的起始端点和终止端点。

2.对能力值从大到小进行排序，按能力值从大到小的顺序加入线段树，能力值相同时，编号小的在前面。

原因：因为每次要查找能力值大于该人且忠诚度最高的那个下属，所以当该点插入线段树时，线段树中已有的节点全部是能力值高于他的人，所以只需要在这群人中，属于其下属的子树区间内查询一下忠诚度的最值即可。
做法：线段树节点用于保存最高忠诚度。细节见代码。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <algorithm>
  5 
  6 #define lson l, m, rt << 1
  7 #define rson m + 1, r, rt << 1 | 1
  8 
  9 using namespace std;
 10 
 11 const int MAXN = 50002;
 12 
 13 struct staff      //员工节点
 14 {
 15     int superior;
 16     int ability;
 17     int loyalty;
 18 };
 19 
 20 struct node       //邻接表保存树
 21 {
 22     int v;
 23     int next;
 24 };
 25 
 26 struct subTree    //存储子树的起始编号和终止编号
 27 {
 28     int st;
 29     int ed;
 30 };
 31 
 32 int N, Q;
 33 int EdgeN, dfs_clock;
 34 //邻接表保存树
 35 node D[MAXN];
 36 int head[MAXN];
 37 
 38 int ans[MAXN];     //存储答案
 39 
 40 staff F[MAXN];
 41 subTree sub[MAXN];   //存储编号为i的员工，其下属的起始编号和终止编号
 42 
 43 int maxi[ MAXN << 2 ];   //线段树，存储忠诚度的最大值
 44 
 45 int vis[ 1000010 ];      //忠诚度→编号映射
 46 
 47 bool cmp( staff a, staff b )
 48 {
 49     return a.ability > b.ability;
 50 }
 51 
 52 void AddEdge( int u, int v )    //头插法加点
 53 {
 54     D[EdgeN].v = v;
 55     D[EdgeN].next = head[u];
 56     head[u] = EdgeN++;
 57     return;
 58 }
 59 
 60 void DFS( int cur )             //DFS遍历，记录其子树的起始编号和终止编号
 61 {
 62     sub[cur].st = dfs_clock++;
 63     for ( int i = head[cur]; i != -1; i = D[i].next )
 64         DFS( D[i].v );
 65     sub[cur].ed = dfs_clock;
 66 }
 67 
 68 void init()                     //初始化
 69 {
 70     EdgeN = 1;
 71     memset( head, -1, sizeof(head) );
 72     memset( maxi, -1, sizeof(maxi) );
 73     dfs_clock = 1;
 74     return;
 75 }
 76 
 77 int query( int L, int R, int l, int r, int rt )   //区间查最值
 78 {
 79     if ( L <= l && r <= R ) return maxi[rt];
 80 
 81     int m = ( l + r ) >> 1;
 82 
 83     int ret = -1;
 84     if ( L <= m ) ret = max( ret, query( L, R, lson ) );
 85     if ( R > m )  ret = max( ret, query( L, R, rson ) );
 86 
 87     return ret;
 88 }
 89 
 90 void PushUp( int rt )
 91 {
 92     maxi[rt] = max( maxi[ rt << 1 ], maxi[ rt << 1 | 1 ] );
 93     return;
 94 }
 95 
 96 void update( int id, int val, int l, int r, int rt )   //节点加入线段树
 97 {
 98     if ( l == id && r == id )
 99     {
100         maxi[rt] = val;
101         return;
102     }
103 
104     int m = ( l + r ) >> 1;
105     if ( id <= m ) update( id, val, lson );
106     else update( id, val, rson );
107 
108     PushUp( rt );
109     return;
110 }
111 
112 int main()
113 {
114     int T;
115     scanf( "%d", &T );
116     while ( T-- )
117     {
118         init();
119 
120         scanf( "%d%d", &N, &Q );
121         for ( int i = 1; i < N; ++i )
122         {
123             int a, aby, loy;
124             scanf( "%d%d%d", &a, &loy, &aby );
125             AddEdge( a, i );
126             F[i].ability = aby;
127             F[i].loyalty = loy;
128             F[i].superior = a;
129             vis[loy] = i;
130         }
131 
132         DFS( 0 );  //根节点编号为0
133 
134         sort( F + 1, F + N, cmp );  //按能力值从大到小排序
135 
136         int j;
137         for ( int i = 1; i < N; i = j )
138         {
139             j = i;
140             while ( j < N && F[i].ability == F[j].ability )
141             {
142                 int id = vis[ F[j].loyalty ];
143                 int tp = -1;
144                 if ( sub[id].st + 1 <= sub[id].ed - 1 )
145                     tp = query( sub[id].st + 1, sub[id].ed - 1, 1, dfs_clock - 1, 1 );
146                 if ( tp == -1 ) ans[id] = -1;
147                 else ans[id] = vis[tp];
148                 ++j;
149             }
150 
151             j = i;
152             while ( j < N && F[i].ability == F[j].ability )
153             {
154                 int id = vis[ F[j].loyalty ];
155                 update( sub[id].st, F[j].loyalty, 1, dfs_clock - 1, 1 );
156                 ++j;
157             }
158         }
159 
160         while ( Q-- )
161         {
162             int a;
163             scanf( "%d", &a );
164             printf( "%d\n", ans[a] );
165         }
166     }
167     return 0;
168 }