POJ3321Apple Tree Dfs序树状数组

2023-02-14 12:08:39

出自——博客园-zhouzhendong

~去博客园看该题解~

题目

POJ3321 Apple Tree

题意概括

有一颗01树，以结点1为树根，一开始所有的结点权值都是1，有两种操作：

　　1.改变其中一个结点的权值（0变1，1变0）

　　2.询问子树X的节点权值和。

输入描述

一组数据。

先是一个数n，表示有n个节点。

接下去n-1行，每行表示一条边。

然后一个数m，表示有m个操作。

然后m行，每行一个字母一个数x，如果字母是Q，则是询问；否则是修改。

输出描述

每一个询问一行，表示答案。

题解

直接把题目变成dfs序上单点修改和区间sum询问的问题。

单点修改，不用线段树，树状数组就可以了。

如果你非要用线段树我也不拦你……

代码

#pragma comment(linker,"/STACK:1024000000,1024000000")

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=+,M=N*;

struct Edge{

    int cnt,y[M],nxt[M],fst[N];

    void set(){

        cnt=;

        memset(fst,,sizeof fst);

    }

    void add(int a,int b){

        y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt;

    }

}e;

int n,m;

int in[N],out[N],time;

int tree[N],v[N];//树状数组

int lowbit(int x){

    return x&-x;

}

void dfs(int prev,int rt){

    in[rt]=++time;

    for (int i=e.fst[rt];i;i=e.nxt[i])

        if (e.y[i]!=prev)

            dfs(rt,e.y[i]);

    out[rt]=time;

}

void update(int x,int d){

    for (;x<=n;x+=lowbit(x))

        tree[x]+=d;

}

int sum(int x){

    int ans=;

    for (;x>;x-=lowbit(x))

        ans+=tree[x];

    return ans;

}

int query(int L,int R){

    return sum(R)-sum(L-);

}

int main(){

    e.set();

    scanf("%d",&n);

    for (int i=,a,b;i<n;i++){

        scanf("%d%d",&a,&b);

        e.add(a,b);

        e.add(b,a);

    }

    time=;

    dfs(,);

    for (int i=;i<=n;i++)

        tree[i]=lowbit(i),v[i]=;

    scanf("%d",&m);

    for (int i=,x;i<=m;i++){

        char ch[];

        scanf("%s%d",ch,&x);

        if (ch[]=='Q')

            printf("%d\n",query(in[x],out[x]));

        else

            update(in[x],-v[x]*),v[x]^=;

    }

    return ;

}

码农公寓