TIOJ 1272 The Agency

[線段樹+壓樹]
發現vector不能來存子節點QQ
1. 壓扁樹
2. 線段樹

#include<cstdio>
#include<stdlib.h>
#include<cstring>
#include<math.h>
#include<vector>
#define N 200000
using namespace std;
//壓扁樹
int NodeLptr[N];
int NodeRptr[N];
int Lineprc=0;
int n,Q;
struct ND
{
    int a;
    ND *next;
}NDs[N];
void SetTreeLine(int node)
{
    NodeLptr[node]=Lineprc+1;
    Lineprc++;
    for(ND *ptr=&NDs[node];ptr->a>0;ptr=ptr->next)
        SetTreeLine(ptr->a-1);
    NodeRptr[node]=Lineprc+1;
    Lineprc++;
}

//線段樹
int base;
bool BST[N*8];
void BuildTree()
{
    base=(int) pow(2,ceil(log2(2*n)))-1;
    if((base+1)==(2*n))
        base=base*2+1;
    // DELETE ?
    //memset(BST,false,sizeof(BST));
}
void Edit(int inp)
{
    int a=NodeLptr[inp-1];
    int b=NodeRptr[inp-1];
    for(a+=base-1,b+=base+1;a^b^1;a>>=1,b>>=1)
    {
        if(~a&1)BST[a^1]=1-BST[a^1];
        if(b&1)BST[b^1]=1-BST[b^1];
    }
    return;
}
bool Ask(int inp)
{
    int cnt=0;
    for(int prc=NodeRptr[inp-1]+base;prc;prc>>=1)
        cnt+=BST[prc];
    return (cnt%2);
}

int main()
{
    scanf("%d %d",&n,&Q);
    int cnt;
    for(int lx=0;lx<n;lx++)
    {
        scanf("%d",&cnt);
        ND *ptr=&NDs[lx];
        for(int ly=0;ly<cnt;ly++)
        {
            int inp;
            scanf("%d",&inp);
            ptr->a=inp;
            ND *newND=(ND*)malloc(sizeof(ND));
            ptr->next=newND;
            ptr=newND;
            //child[lx].push_back(inp);
        }
        ptr->a=-1;
    }
    SetTreeLine(0);
    BuildTree();
    int a,b;
    while(Q--)
    {
        scanf("%d %d",&a,&b);
        if(a==0)
            Edit(b);
        else
            printf("%d\n",Ask(b));
    }
    return 0;
}