HDU4366 Successor 【线段树+DFS】

【题目大意】

有T组数据；

包括boss在内一共有n个员工，boss的编号为0，给出他的上司，每个员工有忠诚度和能力两种属性；

有m个询问操作，当员工k被解雇时，顶替他的员工编号；//注意是询问！并不是真的解雇了！不要跟我一样想那么多乱七八糟的！

遵循的原则是：在员工k的所有下属中找出能力值大于他并且忠诚度最高的员工（忠诚度相同时取编号较小的）；

【分析】

如果只看忠诚度，就与HDU1754基本相似，简单的最大值线段树。（OK又是一个坑掉的题解）

于是我们自然而然的就想到在线段树中维护忠诚度这个性质，那么如何处理能力值？

如果我们在建树的时候先插入能力值大的，那么我们在往后的处理中将不会遇到比当前能力值更大的人了。

OK到这里大概的框架就有了，计划通！

然后我们需要细化一下具体的步骤：

根据线段树的基本性质，编号为rt的节点的两个子节点序号分别为rt*2和rt*2+1，但是这里的员工编号并不满足这样的关系

学习了别人的算法后，这里应该用DFS得到遍历顺序，作为他们在线段树里的编号。

方法是：将每个人的下属保存起来（son），用L和R两个数组记录进出DFS递归的时间

那么对于员工k，他的树编号为L[k]，该节点表示的区间为[L[k+1,R[k]-1]

然后根据能力值由大到小排个序，按大小建树

然后就是线段树中单点修改和区间查询的基本操作（的变形）了 （想把线段树基操也写题解，又一个，何必呢）

单点修改 节点保存子节点中的最大忠诚度值（因为忠诚度唯一，所以map一下员工编号）

区间查询 查询这一节点表示的区间中的最大忠诚度值，并维护在ans数组中

于是m次询问x就可以直接ans[x]辽

【AC代码】

特别注意 maxn是50005WA 改大就过了 玄学题目

#include<iostream>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<vector>
#include<map>
#define maxn 100003
using namespace std;
struct node
{
int id,loty,abty;
}peo[maxn];
vector<int> son[maxn];
int n,tot,m,T,fa;
int ans[maxn],tree[maxn*4],L[maxn],R[maxn];
map<int,int>D;
void init()
{
D.clear();
memset(L,0,sizeof(L));
memset(R,0,sizeof(R));
for (int i=0;i<maxn;i++)
ans[i]=tree[i]=-1,son[i].clear();
tot=0;
}
void dfs(int root)
{
L[root]=tot++;
for (int i=0;i<son[root].size();i++) dfs(son[root][i]);
R[root]=tot;
}
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 m=(l+r)/2;
if(k<=m) update(k,val,rt*2,l,m);
else update(k,val,rt*2+1,m+1,r);
tree[rt]=max(tree[rt*2],tree[rt*2+1]);
}
int ask(int ll,int rr,int rt,int l,int r)//区间查询
{
if (ll>rr) return -1;
if (ll<=l&&r<=rr)
{
return tree[rt];
}
int m=(l+r)/2,ansl=-1,ansr=-1;
if(ll<=m) ansl=ask(ll,rr,rt*2,l,m);
if(rr>m) ansr=ask(ll,rr,rt*2+1,m+1,r);
return max(ansl,ansr);
}
int main()
{
scanf("%d",&T);
while (T--)
{
init();
scanf("%d%d",&n,&m);
for (int i=1;i<n;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;
}
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;
}
while (m--)
{
int xx;
scanf("%d",&xx);
printf("%dn",ans[xx]);
}
}
return 0;
} 

睡觉！摔！

最后

以上就是陶醉朋友为你收集整理的HDU4366 Successor 【线段树+DFS】的全部内容，希望文章能够帮你解决HDU4366 Successor 【线段树+DFS】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。