本文主要是介绍HDU 4366 Successor，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题是一道标准的线段树的题目
题意：sean拥有一家公司，有时他会想要解雇某个人，因此会需要从这个人的下属中找到一个能力值高于他，忠诚度在满足条件的情况下最高的一个人来替代它。要求输出替代的人的编号。
首先题意要理解，在给的数据中的ai是指i的上级的编号，而不是优先级。
然后我们就可以将上下级关系所构成的树构建起来，并且通过DFS序将其转化为一个线性结构（Din,Dout），按照能力值的顺序依次插入对应的员工，在插入之前先查找其对应的线性结构内忠诚度最高的人。而在这里就有一个问题:如果两个人能力值相同，该怎么办？当然是应该插入在关系树中深度较低的员工。因为若下属可以替代上级，那么必须是能力值高于他。先插入上级并不会影响下级的查询。网上有的代码是按照读入顺序插入的，那应该是数据水了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root 1,limit,1
using namespace std;
const int SIZEN=50005;
struct Staff{int abi,loy;int id,level;
};
struct edge{int to,next;
};
int head[SIZEN],sz;
int Din[SIZEN],Dout[SIZEN];
int nid[SIZEN<<2],ans[SIZEN];
bool vis[SIZEN];
int dfs_clock;
edge e[SIZEN<<1];
Staff ss[SIZEN];
void init(){memset(head,-1,sizeof(head));memset(ans,-1,sizeof(ans));memset(vis,0,sizeof(vis));sz=0;dfs_clock=0;ss[0].loy=-1;ss[0].id=-1;ss[0].level=0;
}
void addedge(int u,int v){e[sz].to=v;e[sz].next=head[u];head[u]=sz++;
}
void dfs(int u){if(vis[u]) return;vis[u]=1;dfs_clock++;Din[u]=dfs_clock;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;ss[v].level=ss[u].level+1;dfs(v);}Dout[u]=dfs_clock;
}
int cmp(Staff a,Staff b){if(a.abi!=b.abi) return a.abi>b.abi;else return a.level>b.level;
}
void pushup(int rt){if(ss[nid[rt<<1]].loy>ss[nid[rt<<1|1]].loy)nid[rt]=nid[rt<<1];else nid[rt]=nid[rt<<1|1];
}
void build(int l,int r,int rt){nid[rt]=0;if(l==r) return;int mid=(l+r)>>1;build(lson);build(rson);
}
void update(int loc,int i,int l,int r,int rt){if(l==r){nid[rt]=i;return;}int mid=(l+r)>>1;if(loc<=mid) update(loc,i,lson);else update(loc,i,rson);pushup(rt);
}
int query(int L,int R,int l,int r,int rt){if(L<=l&&r<=R){return nid[rt];}int mid=(l+r)>>1;int ans=0;if(L<=mid){int i=query(L,R,lson);if(ss[i].loy>ss[ans].loy)ans=i;}if(mid+1<=R){int i=query(L,R,rson);if(ss[i].loy>ss[ans].loy)ans=i;}return ans;
}
int main()
{//freopen("data.in","r",stdin);int i,j;int m,n,_;int t,limit;scanf("%d",&_);while(_--){init();scanf("%d%d",&n,&m);for(i=1;i<n;i++){int u;scanf("%d%d%d",&u,&ss[i].loy,&ss[i].abi);ss[i].id=i;addedge(u,i);addedge(i,u);}dfs(0);sort(ss+1,ss+n,cmp);//for(i=0;i<n;i++) printf("%d %d\n",Din[i],Dout[i]);limit=dfs_clock;build(root);for(i=1;i<n;i++){int l=Din[ss[i].id];int r=Dout[ss[i].id];int Max=query(l,r,root);ans[ss[i].id]=ss[Max].id;update(Din[ss[i].id],i,root);}for(i=0;i<m;i++){scanf("%d",&t);if(ans[t]==0) printf("-1\n");else printf("%d\n",ans[t]);}}return 0;
}这篇关于HDU 4366 Successor的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
