线段树
map离散化,按照能力值排序建立更新节点,区间查询(单点更新)
for (int i=1;i<=n-1;i++)
{ scanf("%d%d%d",&fa,&peo[i].loty,&peo[i].abty);
peo[i].id=i;
son[fa].push_back(i);
D[peo[i].loty]=i;
}
离散化
cmp排序(能力相同返回序号小的)
bool cmp(node A,node B){
if (A.abty==B.abty) return A.id<B.id;
else return A.abty>B.abty;
}
单点更新
void update(int k,int val,int rt,int l,int r){
if (l==r) {
tree[rt]=val;return;
}
int mid=(l+r)>>1;
if (k<=mid) update(k,val,rt<<1,l,mid);
else update(k,val,rt<<1|1,mid+1,r);
tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}
区间查询
int ask(int L,int R,int rt,int l,int r){
if (L>R) return -1;
if (L<=l&&r<=R) return tree[rt];
int mid=(l+r)>>1,ansl=-1,ansr=-1;
if (L<=mid) ansl=ask(L,R,rt<<1,l,mid);
if (R>mid) ansr=ask(L,R,rt<<1|1,mid+1,r);
return max(ansl,ansr);
}
dfs序树
今天刚学了taijian,还是挺好理解的(vector写法)
void dfs(int u)
{
L[u]=tot++;
for (int i=0;i<son[u].size();i++) dfs(son[u][i]);
R[u]=tot;
}
邻接表写法
void dfs(int u)
{
l[u]=tot++;
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
dfs(v);
}
r[u]=tot;
}
ans 边处理边记录,化查询为离线
dfs(0);
sort(peo+1,peo+n,cmp);//按能力值排序
for (int i=1;i<n;i++){
int id=peo[i].id;
update(L[id],peo[i].loty,1,0,n-1);
if (son[id].size()==0){
ans[id]=-1;
continue;
}
int s=ask(L[id]+1,R[id]-1,1,0,n-1);
if (s!=-1) ans[id]=D[s];
else ans[id]=-1;
}