首页 > 代码库 > hdu4366 Successor （dfs序+zkw线段树）
hdu4366 Successor （dfs序+zkw线段树）
Successor
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2559 Accepted Submission(s): 613
Problem Description
Sean owns a company and he is the BOSS.The other Staff has one Superior.every staff has a loyalty and ability.Some times Sean will fire one staff.Then one of the fired man’s Subordinates will replace him whose ability is higher than him and has the highest loyalty for company.Sean want to know who will replace the fired man.
Input
In the first line a number T indicate the number of test cases. Then for each case the first line contain 2 numbers n,m (2<=n,m<=50000),indicate the company has n person include Sean ,m is the times of Sean’s query.Staffs are numbered from 1 to n-1,Sean’s number is 0.Follow n-1 lines,the i-th(1<=i<=n-1) line contains 3 integers a,b,c(0<=a<=n-1,0<=b,c<=1000000),indicate the i-th staff’s superior Serial number,i-th staff’s loyalty and ability.Every staff ‘s Serial number is bigger than his superior,Each staff has different loyalty.then follows m lines of queries.Each line only a number indicate the Serial number of whom should be fired.
Output
For every query print a number:the Serial number of whom would replace the losing job man,If there has no one to replace him,print -1.
Sample Input
13 20 100 991 101 10012
Sample Output
2-1
题意： 给一棵树，每个结点有两个值a和b，再有m个查询，查询问一个点的编号u，要求找出u的后代中某个结点v，v.a值比u.a大，v.b是所有后代中最大的那个点编号
思路： 先按照员工关系构出一棵树， 然后将树的dfs深度序列转化为线性序列，按这个序列确定各员工在线段树中的位置。将员工按ability从大到小排序，然后逐个插入线段树相应位置，每次插入前查询以其为根的子树区间中loyalty的最大值及其对应员工。处理完上面之后，对于询问O(1)输出。
代码：
C++交会RE，然后要手动加栈，时间200+ms
G++不需要手动加栈就过了，时间300+ms
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <stack>using namespace std;const int N = 50010;struct _edge{ int to,next;};_edge edge[N*2];int ecnt,head[N];void addedge(int u,int v){ edge[ecnt].to = v; edge[ecnt].next = head[u]; head[u] = ecnt++;}struct node{ int id,a,b,l,r; friend bool operator < (const node &a, const node &b) { return a.a>b.a; }};int n,m,M;int zkw[N*10][2];node man[N];int ans[N];int dfscnt;void dfs(int u,int fa){ man[u].l = dfscnt++; for(int e=head[u];e!=-1;e=edge[e].next) { int &v = edge[e].to; if(v==fa) continue; dfs(v,u); } man[u].r = dfscnt++;}void add(int x,int a,int b){ for(x+=M;x;x>>=1) if(zkw[x][0]<a) zkw[x][0]=a,zkw[x][1]=b;}int query(int l,int r){ int a,b; a=b=-1; for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1) { if(~l&1 && zkw[l^1][0]>a) a=zkw[l^1][0],b=zkw[l^1][1]; if(r&1 && zkw[r^1][0]>a) a=zkw[r^1][0],b=zkw[r^1][1]; } return b;}void run(){ scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); ecnt=0; int a,b,c; for(int i=1;i<n;i++) { scanf("%d%d%d",&a,&b,&c); addedge(a,i); addedge(i,a); man[i].a=c; man[i].b=b; man[i].id=i; } dfscnt=1; dfs(0,-1);// for(int i=0;i<n;i++)// printf("%d %d %d\n",i,man[i].l,man[i].r); sort(man+1,man+n); for(M=1;M<=dfscnt+1;M*=2); memset(zkw,-1,sizeof(zkw)); stack<int> stk; stk.push(1); ans[man[1].id]=-1; for(int i=2;i<n;i++) { if(man[i].a!=man[i-1].a) { while(!stk.empty()) { int u = stk.top(); stk.pop(); add(man[u].l,man[u].b,man[u].id); add(man[u].r,man[u].b,man[u].id); } } stk.push(i); ans[man[i].id] = query(man[i].l,man[i].r); } while(m--) { scanf("%d",&a); printf("%d\n",ans[a]); }}int main(){ freopen("case.txt","r",stdin); int _; scanf("%d",&_); while(_--) run(); return 0;}
hdu4366 Successor （dfs序+zkw线段树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。