xmu 1466.祖先极值

1466.祖先极值
Time Limit: 5000 MS Memory Limit: 131072 K
Total Submissions: 153 (39 users) Accepted: 43 (25 users)
[ My Solution]

Description
在一棵有向树中, 若节点u至节点v之间有一条有向边, 则我们称u为v的父节点, 也可以称作1祖先节点。所谓节点v的k祖先节点, 指的是节点v的父节点的k-1祖先节点。现在, 给定你一棵以0为根节点的树, 树上的每个节点都有一个值, 你需要能快速的回答出从节点v至它的k祖先节点所经过的所有节点中(即v节点、v节点的1祖先、...、v节点的k-1祖先、v节点的k祖先), 值最大的节点的值的为多少? 其中我们默认0号节点的值为0。

Input
输入的第一行有一个正整数n (n <= 100,000), 接下来的一行有n个整数ai(1 <= i <= n, 1 <= ai <= 1,000,000,000), 第i个数字代表了第i号节点上的数值。再接下来的一行有n个正整数bi(1 <= i <= n, 0 <= bi < i), 第i个数字代表了第i号节点的父节点的为bi。再接下来有一个整数m (1 <= m <= 100,000), 代表了询问的次数, 接下来的m行, 每行有2个整数k, v (1 <= k <= n, 1 <= v <= n), 代表了询问, 从v节点到它的k祖先所经历的所有节点中的最大值。

Output
对于每次询问, 若v节点不存在k祖先, 则输出一行"Wrong request", 否则输出一个整数, 代表了从v节点到它的k祖先所经历的所有节点中的最大值。

Sample Input
5
1 2 2 1 3
0 0 1 1 2
4
1 4
2 2
2 3
1 5

Sample Output
1
Wrong request
2
3
唉，我真是太笨了，看了别人的代码才会做，就是以树的高度作为区间查询
妹的，苦逼的调试
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100010
#define l(i) i<<1
#define r(i) i<<1|1
struct node{
    int l,r,mx;
}T[N*4];
int mx;
struct Data{
    int x,id;
};
int v[N],ans[N];//值,答案
vector<Data>a[N];
vector<int>son[N];
void build(int l,int r,int k){
    T[k].l=l;
    T[k].r=r;
    T[k].mx=0;
    if(l==r)return;
    int mid=(l+r)/2;
    build(l,mid,l(k));
    build(mid+1,r,r(k));
}
int insert(int d,int k,int v){//值k插入区间[d,d]
    if(T[k].l==T[k].r)return T[k].mx=v;
    int ll=l(k);
    int rr=r(k);
    if(T[ll].r>=d)insert(d,ll,v);//往左
    else if(T[rr].l<=d) insert(d,rr,v);//往右
    return T[k].mx=max(T[ll].mx,T[rr].mx);
}
void query(int l,int r,int k){//查询区间[l,r]
    if(T[k].l==l&&T[k].r==r){
        mx=max(mx,T[k].mx);
        return;
    }
    int ll=l(k);
    int rr=r(k);
    if(T[ll].r>=r)query(l,r,ll);//往左
    else if(T[rr].l<=l)query(l,r,rr);//往右
    else{
        query(l,T[ll].r,ll);//往左
        query(T[rr].l,r,rr);//往右
    }
}
void dfs(int x,int d){
    int i,j,k;
    insert(d,1,v[x]);//插入v
    //cout<<"插入"<<x<<" "<<v[x]<<endl;
    for(i=0;i<a[x].size();i++){//查询x结点
        k=d-a[x][i].x;
        mx=-1;
        if(k>=0)query(k,d,1);
        ans[a[x][i].id]=mx;
        //cout<<x<<" "<<k<<" "<<d<<" "<<mx<<endl;
    }
    for(i=0;i<son[x].size();i++)//遍历儿子
        dfs(son[x][i],d+1);//递归遍历
}
int main(){
    int n,i,j,k;
    v[0]=0;
    struct Data s;
    while(scanf("%d",&n)!=EOF){
        memset(a,0,sizeof(a));
        memset(son,0,sizeof(son));
        build(0,n-1,1);//建立空树
        for(i=1;i<=n;i++)scanf("%d",&v[i]);
        for(i=1;i<=n;i++){
            scanf("%d",&j);
            son[j].push_back(i);//i是j的儿子
        }
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%d%d",&j,&k);
            s.x=j;s.id=i;
            a[k].push_back(s);
        }
        /*for(i=0;i<=n;i++){
            cout<<i<<":";
            for(j=0;j<son[i].size();j++){
                cout<<son[i][j]<<" ";
            }
            cout<<endl;
        }*/
        dfs(0,0);//从根遍历到最后
        for(i=0;i<n;i++)
            if(ans[i]==-1)printf("Wrong request\n");
                else printf("%d\n",ans[i]);
    }
return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define N 100010
#define l(i) i<<1
#define r(i) i<<1|1
struct node{
int l,r,mx;
}T[N*4];
int mx;
struct Data{
int x,id;
};
int v[N],ans[N];//值,答案
vector<Data>a[N];
vector<int>son[N];
void build(int l

补充：软件开发 , C++ ,