TIOJ 1493 三個農夫

poao899    1493    Accepted    37884K    1510MS    G++    2.79K    2010-04-03 13:49:36                 .


死得亂七八糟==


反正就  壓扁線段樹  但是一直co炸= =





不會Stack Overflow超神奇










//************************************

#include<stdio.h>
#include<stdlib.h>
#define MAXV 1000100
int conv[MAXV][2], _opt, _t, _n, _m, _pos, a, b;
long long  _adj;
char com[100];

template<class T>
T getnum(){
    T get = 0;
    char c = getchar();
    while(c == ' ' || c == '\n') c = getchar();
    while(c > 47 && c < 58){
        get = get * 10 + c - 48;
        c = getchar();
    }
    return get;
}

//Tree
struct edge{
    int j;
    edge *next;
}e[MAXV*2],*v[MAXV];
void set(int i, int j){
    static int cnt=0;
    edge *p= v[i], *q= e+cnt++;
    v[i]= q; q->j= j; q->next= p;
}
//DFS
void dfs(int now){
    conv[now][0]= ++_t;
    for(edge *p=v[now]; p; p=p->next){
        if(conv[p->j][0])continue;
        dfs(p->j);
    }
    conv[now][1]= ++_t;
}
//Segment_Tree 2/e
struct seg{
    int l, r; long long v[3];
    seg *lch, *rch;
    long long qry(int, int);
    void adj();
}s[MAXV*4],*st;
seg* get(int l, int r){
    static int cCnt=0;
    seg *p= s+cCnt++;
    p->l=l; p->r=r; p->v[0]=p->v[1]=p->v[2]=-1; p->lch=p->rch=NULL;
    return p;
}
long long seg::qry(int _l, int _r){
    if(_l<l|| _r>r)return 0;
    if(l==r)return v[_opt]==-1? v[_opt]=0: v[_opt];
    int mid= (l+r)/2;
    if(!lch)return 0;
    if(_l==l&& _r==r){
        if(v[_opt]== -1){
            return v[_opt]= lch->qry(l, mid) + rch->qry(mid+1, r);
        }else return v[_opt];
    }
    if(mid>= _r)return lch->qry(_l, _r);
    else if(mid< _l)return rch->qry(_l, _r);
    return lch->qry(_l, mid) + rch->qry(mid+1, _r);
}
void seg::adj(){
    if(_pos<l|| _pos>r)return;
    int mid= (l+r)/2;
    if(l==r){
        if(v[_opt]== -1)v[_opt]=0;
        v[_opt]+= _adj; return;
    }
    if(!lch){
        lch= get(l, mid);
        rch= get(mid+1, r);
    }
    if(v[_opt]!= -1)v[_opt]+= _adj;
    if(mid< _pos) rch->adj();
    else lch->adj();
}
int main(){
    _n = getnum<int>();
    //Init
    st= get(1, _n*2);
    for(int i=1; i<_n; i++){
        a= getnum<int>(); b= getnum<int>();
        set(a, b); set(b, a);
    }
    //DFS : to Seg Tree
    dfs(1);
    scanf("%d", &_m);
    for(int i=0; i<_m; i++){
        scanf("%s", com);
        switch(com[0]){
            case'Q':
                _pos= getnum<int>();
                a= conv[_pos][0]; b= conv[_pos][1];
                for(_opt=0; _opt<3; _opt++,putchar(_opt==3?'\n':' '))
                    printf("%I64d", st->qry(a,b));
                break;
            case'D':
                _pos= getnum<int>(); _opt=getnum<int>();
                _adj= getnum<long long>();
                a= conv[_pos][0]; b= conv[_pos][1];
                if(_pos==1&& _opt!=2 || _pos!=1&&b==a+1&&_opt==2){
                    puts("Error");
                }else{
                    long long q= st->qry(a, a);
                    //printf("Q %I64d\n", q);
                    if(q>= _adj){
                        _adj= -_adj;
                        _pos= a;
                        st->adj();
                    }else puts("Error");
                }
                break;
            case'G':
                _pos= getnum<int>(); _opt=getnum<int>();
                _adj= getnum<long long>();
                a= conv[_pos][0]; b= conv[_pos][1];
                if(_pos==1&& _opt!=2 || _pos!=1&&b==a+1&&_opt==2){
                    puts("Error");
                }else{
                    a= conv[_pos][0];
                    _pos= a;
                    st->adj();
                }
                break;
        }
    }
}