2012 Multi-University Training Contest 7

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #define tl (p << 1)
  6 #define tr (p << 1 | 1)
  7 using namespace std;
  8 const int LEN = 1e5 + 5;
  9 int i,j,k,n,m,s,t,tot,Time;
 10 struct edge {
 11     int vet,next;
 12 } E[LEN * 2];
 13 struct node {
 14     int x,y,id;
 15 } a[LEN];
 16 bool cmp(const node &x,const node &y) {
 17     return x.x > y.x;
 18 };
 19 int head[LEN],size[LEN],tid[LEN],ans[LEN],pre[LEN],b[LEN];
 20 int to[1000005];
 21 int tmax[LEN * 4];
 22 void add(int u,int v) {
 23     E[++tot] = (edge){v,head[u]};
 24     head[u] = tot;
 25 }
 26 void dfs(int u) {
 27     size[u] = 1;
 28     tid[u] = ++Time;
 29     pre[Time] = u;
 30     for (int e = head[u]; e != -1; e = E[e].next) {
 31         int v = E[e].vet;
 32         dfs(v);
 33         size[u] += size[v];
 34     }
 35 }
 36 int ask(int l,int r,int x,int y,int p) {
 37     if (l == x && y == r) {
 38         return tmax[p];
 39     }
 40     int mid = (l + r) >> 1;
 41     if (mid >= y) {
 42         return ask(l,mid,x,tl);
 43     } else if (mid + 1 <= x) {
 44         return ask(mid + 1,r,tr);
 45     } else {
 46         return max(ask(l,tl),ask(mid + 1,mid + 1,tr));
 47     }
 48 }
 49 void update(int p) {
 50     tmax[p] = max(tmax[tl],tmax[tr]);
 51 }
 52 void modify(int l,const int &x,int p,const int &c) {
 53     if (l == r) {
 54         tmax[p] = c;
 55         return;
 56     }
 57     int mid = (l + r) >> 1;
 58     if (mid >= x) {
 59         modify(l,tl,c);
 60     } else {
 61         modify(mid + 1,tr,c);
 62     }
 63     update(p);
 64 }
 65 void build(int l,int p) {
 66     if (l == r) {
 67         tmax[p] = -1;
 68         return;
 69     }
 70     int mid = (l + r) >> 1;
 71     build(l,tl);
 72     build(mid + 1,tr);
 73     update(p);
 74 }
 75 int main() {
 76     int T;
 77     scanf("%d",&T);
 78     while (T--) {
 79         tot = Time = 0;
 80         scanf("%d %d",&n,&m);
 81         for (int i = 1; i <= n; i++) {
 82             head[i] = -1;
 83             size[i] = 0;
 84             tid[i] = 0;
 85         }
 86         a[1] = (node){1e9,0,1};
 87         for (int i = 2; i <= n; i++) {
 88             int fa,y;
 89             scanf("%d %d %d",&fa,&x,&y);
 90             x++,y++,fa++;
 91             swap(x,y);
 92             add(fa,i);
 93             a[i] = (node){x,i};
 94             to[y] = i;
 95         }
 96         dfs(1);
 97         build(1,1);
 98         sort(a + 1,a + 1 + n,cmp);
 99         int j = 1;
100         for (int i = 2; i <= n; i++) {
101             int x = a[i].id,t = ask(1,tid[x],tid[x] + size[x] - 1,1);
102             if (t == -1) {
103                 ans[x] = 0;
104             } else {
105                 ans[x] = to[t];
106             }
107             while (j + 1 <= i && a[j + 1].x > a[i + 1].x) {
108                 modify(1,tid[a[j + 1].id],1,a[j + 1].y);
109                 j++;
110             }
111         }
112         while (m--) {
113             int x;
114             scanf("%d",&x);
115             printf("%dn",ans[x + 1] - 1);
116         }
117     }
118     return 0;
119 }