【hdu4366】dfs序线段树

  1 #include <bits/stdc++.h>
  2 #define ll long long
  3 #define lson l, m, rt<<1
  4 #define rson m+1, r, rt<<1|1
  5 using namespace std;
  6 const int N = 5e4+5;
  7 
  8 vector<int> ve[N];
  9 int b[N], c[N], tot;
 10 int l[N], r[N], ans[N];
 11 void dfs(int fa, int x){
 12     tot++;
 13     l[x] = tot;
 14     for(int i = 0; i < ve[x].size(); i++){
 15         int y = ve[x][i];
 16         if(y == fa) continue ;
 17         dfs(x, y);
 18     }
 19     r[x] = tot;
 20 }
 21 
 22 struct Node{
 23     int b, pos;
 24     Node(){}
 25     Node(int b, int pos): b(b), pos(pos){}
 26     bool operator <(const Node& a) const{
 27         return b < a.b;
 28     }
 29 };
 30 Node T[N<<2];
 31 
 32 void pushup(int rt){
 33     T[rt] = max(T[rt<<1], T[rt<<1|1]);
 34 }
 35 void build(int l, int r, int rt){
 36     T[rt].b = T[rt].pos = -1;
 37     if(l == r) return ;
 38     int m = l+r >> 1;
 39     build(lson);
 40     build(rson);
 41 }
 42 void update(int pos, Node x, int l, int r, int rt){
 43     if(pos == l&&r == pos){
 44         T[rt] = x;
 45         return ;
 46     }
 47     int m = l+r >> 1;
 48     if(pos <= m) update(pos, x, lson);
 49     else update(pos, x, rson);
 50     pushup(rt);
 51 }
 52 Node query(int L, int R, int l, int r, int rt){
 53     if(L <= l&&r <= R)
 54         return T[rt];
 55     int m = l+r >> 1;
 56     Node ret = Node(-1, -1);
 57     if(L <= m) ret = max(ret, query(L, R, lson));
 58     if(R > m) ret = max(ret, query(L, R, rson));
 59     return ret;
 60 }
 61 
 62 struct p{
 63     int b, c, id, kth;
 64     p(){}
 65     p(int b, int c, int id, int kth):b(b), c(c), id(id), kth(kth){}
 66     bool operator < (const p& a) const{
 67         return c != a.c? c > a.c: kth < a.kth;
 68     }
 69 };
 70 p pp[N];
 71 
 72 int main(){
 73     int t; scanf("%d", &t);
 74     while(t--){
 75         int n, m, x;
 76         scanf("%d%d", &n, &m);
 77         for(int i = 0; i < n; i++) ve[i].clear();
 78         b[0] = c[0] = -1;
 79         for(int i = 1; i < n; i++){
 80             scanf("%d%d%d", &x, b+i, c+i);
 81             ve[x].push_back(i);
 82         }
 83 
 84         tot = 0;
 85         dfs(-1, 0);
 86         for(int i = 0; i < n; i++)
 87             pp[i] = p(b[i], c[i], i, l[i]);
 88         sort(pp+1, pp+n);
 89         build(1, n, 1);
 90         for(int i = 1; i < n; i++){
 91             int j = pp[i].id;
 92             int L = l[j]+1, R = r[j];
 93             if(L > R) ans[j] = -1;
 94             else
 95                 ans[j] = query(L, R, 1, tot, 1).pos;
 96             update(l[j], Node(pp[i].b, pp[i].id), 1, tot, 1);
 97         }
 98         while(m--){
 99             scanf("%d", &x);
100             printf("%d
", ans[x]);
101         }
102     }
103     return 0;
104 }
View Code