【hdu4366】dfs序线段树

 #include <bits/stdc++.h>
#define ll long long
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
const int N = 5e4+; vector<int> ve[N];
int b[N], c[N], tot;
int l[N], r[N], ans[N];
void dfs(int fa, int x){
tot++;
l[x] = tot;
for(int i = ; i < ve[x].size(); i++){
int y = ve[x][i];
if(y == fa) continue ;
dfs(x, y);
}
r[x] = tot;
} struct Node{
int b, pos;
Node(){}
Node(int b, int pos): b(b), pos(pos){}
bool operator <(const Node& a) const{
return b < a.b;
}
};
Node T[N<<]; void pushup(int rt){
T[rt] = max(T[rt<<], T[rt<<|]);
}
void build(int l, int r, int rt){
T[rt].b = T[rt].pos = -;
if(l == r) return ;
int m = l+r >> ;
build(lson);
build(rson);
}
void update(int pos, Node x, int l, int r, int rt){
if(pos == l&&r == pos){
T[rt] = x;
return ;
}
int m = l+r >> ;
if(pos <= m) update(pos, x, lson);
else update(pos, x, rson);
pushup(rt);
}
Node query(int L, int R, int l, int r, int rt){
if(L <= l&&r <= R)
return T[rt];
int m = l+r >> ;
Node ret = Node(-, -);
if(L <= m) ret = max(ret, query(L, R, lson));
if(R > m) ret = max(ret, query(L, R, rson));
return ret;
} struct p{
int b, c, id, kth;
p(){}
p(int b, int c, int id, int kth):b(b), c(c), id(id), kth(kth){}
bool operator < (const p& a) const{
return c != a.c? c > a.c: kth < a.kth;
}
};
p pp[N]; int main(){
int t; scanf("%d", &t);
while(t--){
int n, m, x;
scanf("%d%d", &n, &m);
for(int i = ; i < n; i++) ve[i].clear();
b[] = c[] = -;
for(int i = ; i < n; i++){
scanf("%d%d%d", &x, b+i, c+i);
ve[x].push_back(i);
} tot = ;
dfs(-, );
for(int i = ; i < n; i++)
pp[i] = p(b[i], c[i], i, l[i]);
sort(pp+, pp+n);
build(, n, );
for(int i = ; i < n; i++){
int j = pp[i].id;
int L = l[j]+, R = r[j];
if(L > R) ans[j] = -;
else
ans[j] = query(L, R, , tot, ).pos;
update(l[j], Node(pp[i].b, pp[i].id), , tot, );
}
while(m--){
scanf("%d", &x);
printf("%d\n", ans[x]);
}
}
return ;
}
上一篇:20151009 C# 第一篇 程序编写规范


下一篇:UnknownHostException: xxx,使用nacos远程调用服务(负载均衡)报错