CUBE-149: Gui Pachinko

#include<stdio.h>
#include<vector>
#include<algorithm>
typedef long long int ll;
using namespace std;
int n;

vector<int> adj[100010];

int maxsubtree[100010];
int writemax(int u){
    int maxnow = u;
    for(int i = 0 ; i < adj[u].size() ; i ++){
        int v = adj[u][i];
        maxnow = max(maxnow,writemax(v));
    }
    return maxsubtree[u] = maxnow;
}

bool mycmp(int a,int b){
    return maxsubtree[a] < maxsubtree[b];
}

int order = 1;
ll ordernode[100010];

void writeorder(int u){
    for(int i = 0 ; i < adj[u].size() ; i ++){
        int v = adj[u][i];
        writeorder(v);
    }
    ordernode[order++] = u;
}


int main()
{
    int k;
    scanf("%d %d",&n,&k);
    for(int i = 1 ; i <= n ; i ++ ){
        int p;
        scanf("%d",&p);
        adj[p].push_back(i);
    }
    writemax(0);
    for(int i = 1 ; i <= n ; i ++ ){
        sort(adj[i].begin(),adj[i].end(),mycmp);
    }
//  printf("Maxsubtree : ");for(int i = 1 ; i <= n ; i ++)printf("%d ",maxsubtree[i]);printf("\n");
    writeorder(0);
//  printf("Ordernode  : ");for(int i = 1 ; i <= n ; i ++)printf("%d ",ordernode[i]);printf("\n");
    ll qs[n+1];qs[0] = 0;
    for(int i = 1 ; i <= n ; i ++){
        qs[i] = qs[i-1] + ordernode[i];
    }

    int ballnow = 0;
    for(int q = 0 ; q < k ; q ++){
        int op;
        scanf("%d",&op);
        if(op == 1){
            int cnt;
            scanf("%d",&cnt);
            ballnow += cnt;
            printf("%d\n",ordernode[ballnow]);
        }
        else if(op == 2){
            int cnt;
            scanf("%d",&cnt);
            ballnow -= cnt;
        }
        else if(op == 3){
            printf("%lld\n",qs[ballnow]);
        }
        else{
            printf("Error : %d\n",q);
            return 0;
        }
    }
    return 0;
}