HDOJ 4366 - Successor 展開樹為後序周遊,離線處理線段樹..出現問題:讀題錯誤..細節寫錯..爆棧..

              題意:

                         有一個由上下級關系構成的樹...如果開除一個人..那麼從他的子樹裡找一個能力比他強..并且忠誠度最高的(注意..不是比他高)..問若開除誰,,誰來頂替(注意..不是連續的過程..都是單獨的...)

              題解:

                          完全2B了...讀題各種錯誤..連ability和loyalty的讀入都搞反..然後是忠誠度的要求搞錯..排序的時候少考慮了(能力相等..父節點在子節點前面)...寫線段樹的時候又犯些2B的錯誤..而且還莫名其妙的爆棧....隻帶一個參數走..dfs裡也隻定義了一個參數..這也能爆棧？沒辦法..隻能前面加申請棧空間代碼...這題要把我做蒙了..還好送出十多次終于AC了..思路一開始就沒錯...真是蛋疼...

                          題解思路很簡單...離線打表..O(1)輸出...為了友善線段樹的查詢..找出該樹的後序周遊(DFS回朔标記即可...)..發現其孩子都在他左邊的某一片區域...一顆二維的樹就變成了一個一維的...用線段樹點更新.區間查找最大值就好...每個staff按能力大小的順序往線段樹裡添加..每次找他孩子所在區間的忠誠最大值..由于放入的時候保證了是按能力大小..也就是當本staff查詢時..線段樹中所存在staff的能力都比他大..是以隻要找區間忠誠度最高的...

Program:

#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<stack>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define oo 1000000007
#define MAXN 50005
#define ll int
using namespace std; 
struct node
{
       int a,b,l,id;
}s[MAXN];
struct LINE
{
       int x,y,next;
}line[MAXN]; 
int Max[MAXN<<2],_next[MAXN];
int hash[1000005],ans[MAXN],dfn[MAXN],Lnum,N,num;
bool cmp(node a,node b) 
{ 
       if (a.b!=b.b) return a.b>b.b; 
       return dfn[a.id]>dfn[b.id];
}
void addline(int x,int y)
{
       line[++Lnum].next=_next[x],_next[x]=Lnum;
       line[Lnum].x=x,line[Lnum].y=y;
}
void dfs(int x)
{
       s[x].l=oo;
       for (int k=_next[x];k;k=line[k].next) 
       {
             dfs(line[k].y);
             s[x].l=min(s[x].l,s[line[k].y].l);
       }
       dfn[x]=num,s[x].l=min(s[x].l,num); 
       num++;
}
void update(int p,int c,int l,int r,int now)
{
       if (l==r) { Max[now]=c; return; }
       int mid=l+r>>1;
       if (p<=mid) update(p,c,l,mid,now<<1);
       if (p>mid)  update(p,c,mid+1,r,now<<1|1);
       Max[now]=max(Max[now<<1],Max[now<<1|1]); 
}
int query(int L,int R,int l,int r,int now)
{
       if (L<=l && R>=r) return Max[now];
       int mid=l+r>>1,ans=-oo;
       if (L<=mid) ans=max(ans,query(L,R,l,mid,now<<1));
       if (R>mid)  ans=max(ans,query(L,R,mid+1,r,now<<1|1));
       return ans;
}
int main()
{ 
       int cases,i,x,Q;   
       scanf("%d",&cases);
       while (cases--)
       {
                scanf("%d%d",&N,&Q);
                memset(_next,0,sizeof(_next)),Lnum=0;
                for (i=1;i<N;i++)
                {
                        scanf("%d%d%d",&x,&s[i].a,&s[i].b);
                        hash[s[i].a]=i,s[i].id=i;
                        addline(x,i);
                }
                s[0].a=s[0].b=oo; s[0].id=0;
                num=0; 
                dfs(0);
                sort(s,s+N,cmp);
                memset(Max,-0x3f,sizeof(Max)); 
                for (i=0;i<N;i++)
                {
                        x=query(s[i].l,dfn[s[i].id],0,N-1,1);
                        if (x<0) ans[s[i].id]=-1;
                                 else ans[s[i].id]=hash[x];
                        update(dfn[s[i].id],s[i].a,0,N-1,1);
                }
                while (Q--)
                {
                        scanf("%d",&x);
                        printf("%d\n",ans[x]);
                }
       }
       return 0;
}