HDOJ4366解题报告【dfs序+线段树】

题目地址：

　　http://acm.hdu.edu.cn/showproblem.php?pid=4366

题目概述：

　　给出一个公司所有员工的上下级关系（数据保证是一棵树），现在想解雇一些员工，而他们的位置由他们的手下里能力值比他大而且忠诚度最高的人来替代，给出m个询问，求输出替代他们的人的编号。

大致思路：

　　学习了一下dfs序的用法，附学习的博客：http://blog.csdn.net/Miracle_ma/article/details/51485118

　　简单的说dfs序就是将一棵树变成线性结构的算法，并且保证点i的子树都在i的后面。

　　根据dfs序首先将员工之间的关系转化成数组，然后对于员工的数据a按照能力值降序排列，并且将所有的询问q也按对应的能力值降序排列。

　　排完序之后依次插入a中的元素进入线段树中，比较当前插入的a_i与未处理的q中能力值最高的比较，如果a_i的能力值比较小，则处理这个询问，否则继续插入。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <vector>
  6 #include <ctime>
  7 #include <map>
  8 #include <stack>
  9 #include <queue>
 10 #include <cstring>
 11 #include <algorithm>
 12 using namespace std;
 13 
 14 #define sacnf scanf
 15 #define scnaf scanf
 16 #define maxn  50010
 17 #define maxm 26
 18 #define inf 1061109567
 19 #define Eps 0.00001
 20 const double PI=acos(-1.0);
 21 #define mod 7
 22 #define MAXNUM 10000
 23 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
 24 int Abs(int x) {return (x<0)?-x:x;}
 25 typedef long long ll;
 26 typedef unsigned int uint;
 27 
 28 struct node
 29 {
 30     int pos,abi,loy;
 31     bool operator < (const node &a) const
 32     {
 33         if(abi==a.abi) return loy>a.loy;
 34         return abi>a.abi;
 35     }
 36 } a[maxn];
 37 
 38 struct node1
 39 {
 40     int pos,val;
 41 } q[maxn];
 42 
 43 vector<int> G[maxn];
 44 int tme;
 45 int st[maxn],ed[maxn];
 46 int tabi[maxn],tloy[maxn];
 47 int ans[maxn];
 48 int tree[maxn*4];          ///loy最大的点的编号
 49 
 50 bool cmp(node1 a,node1 b)
 51 {
 52     return tabi[a.val]>tabi[b.val];
 53 }
 54 
 55 void dfs(int u,int fa)
 56 {
 57     st[u]=++tme;
 58     int len=G[u].size();
 59     for(int i=0;i<len;i++)
 60     {
 61         int v=G[u][i];
 62         if(v!=fa) dfs(v,u);
 63     }
 64     ed[u]=tme;
 65 }
 66 
 67 void build_tree(int l,int r,int dir)
 68 {
 69     if(l==r)
 70     {
 71         tree[dir]=1;
 72         return;
 73     }
 74     int m=(l+r)>>1;
 75     build_tree(l,m,dir<<1);
 76     build_tree(m+1,r,dir<<1|1);
 77     tree[dir]=1;
 78 }
 79 
 80 void add(int l,int r,int dir,int pos,int val)
 81 {
 82     if(l==r)
 83     {
 84         tree[dir]=(tloy[tree[dir]]<tloy[val])?val:tree[dir];
 85         return;
 86     }
 87     int m=(l+r)>>1;
 88     if(pos<=m) add(l,m,dir*2,pos,val);
 89     else add(m+1,r,dir*2+1,pos,val);
 90     tree[dir]=(tloy[tree[dir*2]]<tloy[tree[dir*2+1]])?tree[dir*2+1]:tree[dir*2];
 91 }
 92 
 93 int query(int l,int r,int dir,int ql,int qr)
 94 {
 95     if(ql>qr) return 1;
 96     if(ql>r||l>qr) return 1;
 97     if(ql<=l&&r<=qr) return tree[dir];
 98     int m=(l+r)>>1,t1,t2;
 99     t1=query(l,m,dir<<1,ql,qr);
100     t2=query(m+1,r,dir<<1|1,ql,qr);
101     return (tloy[t1]<tloy[t2])?t2:t1;
102 }
103 
104 int main()
105 {
106     //freopen("data.in","r",stdin);
107     //freopen("data.out","w",stdout);
108     //clock_t st=clock();
109     int n,m,T;scanf("%d",&T);tree[0]=-1;
110     while(T--)
111     {
112         sacnf("%d%d",&n,&m);
113         int x;
114 
115         a[1].pos=1;a[1].abi=a[1].loy=-1;
116         tloy[1]=tabi[1]=-1;
117         for(int i=1;i<=n;i++) G[i].clear();
118 
119         for(int i=2;i<=n;i++)
120         {
121             scanf("%d%d%d",&x,&a[i].loy,&a[i].abi);
122             x++;a[i].pos=i;tabi[i]=a[i].abi;tloy[i]=a[i].loy;
123             G[x].push_back(i);G[i].push_back(x);
124         }
125 
126         tme=0;
127         dfs(1,-1);
128         build_tree(1,n,1);
129 
130         sort(a+1,a+1+n);       ///按ability降序排列    a-->第i个人的数据
131 
132         for(int i=1;i<=m;i++)                  ///q-->第i个询问的序号及询问编号
133         {
134             scanf("%d",&q[i].val);q[i].val++;
135             q[i].pos=i;
136         }
137         sort(q+1,q+1+m,cmp);          ///按ability降序排列
138 
139         int i=1,j=1;
140         while(i<=m)
141         {
142             int p=a[j].pos;
143             if(a[j].abi<=tabi[q[i].val])
144             {
145                 int temp=query(1,n,1,st[q[i].val]+1,ed[q[i].val]);
146                 ans[q[i].pos]=temp-1;i++;
147                 if(i>m) break;
148             }
149             else if(j<n)
150             {
151                 add(1,n,1,st[p],p);j++;
152             }
153         }
154         for(i=1;i<=m;i++) printf("%d
",(ans[i]==0)?-1:ans[i]);
155     }
156     //clock_t ed=clock();
157     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
158     return 0;
159 }