苹果树（codevs 1228）

题目描述 Description

在卡卡的房子外面，有一棵苹果树。每年的春天，树上总会结出很多的苹果。卡卡非常喜欢吃苹果，所以他一直都精心的呵护这棵苹果树。我们知道树是有很多分叉点的，苹果会长在枝条的分叉点上面，且不会有两个苹果结在一起。卡卡很想知道一个分叉点所代表的子树上所结的苹果的数目，以便研究苹果树哪些枝条的结果能力比较强。

卡卡所知道的是，每隔一些时间，某些分叉点上会结出一些苹果，但是卡卡所不知道的是，总会有一些调皮的小孩来树上摘走一些苹果。

于是我们定义两种操作：

C x	表示编号为x的分叉点的状态被改变(原来有苹果的话，就被摘掉，原来没有的话，就结出一个苹果)
G x	查询编号为x的分叉点所代表的子树中有多少个苹果

我们假定一开始的时候，树上全都是苹果，也包括作为根结点的分叉1。

输入描述 Input Description

第一行一个数N (n<=100000)

接下来n-1行,每行2个数u,v,表示分叉点u和分叉点v是直接相连的。

再接下来一行一个数M,(M<=100000)表示询问数

接下来M行,表示询问,询问的格式如题目所述Q x或者C x

输出描述 Output Description

对于每个Q x的询问,请输出相应的结果,每行输出一个

样例输入 Sample Input

1 2

1 3

Q 1

C 2

Q 1

样例输出 Sample Output

/*

  用暴力写到了80分，剩下两个点就无力回天了。

  正解：dfs序+线段树（或树状数组）

  先跑一遍dfs，维护出两个数组，in[i]表示i这个点的dfs序编号，out[i]表示i这颗子树最后一个节点标号那么当我们修改i时就是修改in[i]，查询i时就是查询in[i]-out[i]这个区间，剩下的交由线段树处理。

*/

#include<cstdio>

#include<iostream>

#define lson l,mid,now*2

#define rson mid+1,r,now*2+1

#define M 100010

using namespace std;

int sum[M*],head[M],in[M],out[M],vis[M],n,m,cnt;

struct node

{

    int v,pre;

};node e[M];

void add(int i,int x,int y)

{

    e[i].v=y;

    e[i].pre=head[x];

    head[x]=i;

}

void dfs(int x)

{

    in[x]=++cnt;

    for(int i=head[x];i;i=e[i].pre)

      dfs(e[i].v);

    out[x]=cnt;

}

void push_up(int now)

{

    sum[now]=sum[now*]+sum[now*+];

}

void change(int pos,int v,int l,int r,int now)

{

    if(l==r)

    {

        sum[now]+=v;

        return;

    }

    int mid=(l+r)/;

    if(pos<=mid)change(pos,v,lson);

    else change(pos,v,rson);

    push_up(now);

}

int query(int x,int y,int l,int r,int now)

{

    if(l>=x&&r<=y)return sum[now];

    int mid=(l+r)/;

    int ans=;

    if(x<=mid) ans+=query(x,y,lson);

    if(y>mid) ans+=query(x,y,rson);

    return ans;

}

int main()

{

    scanf("%d",&n);

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

    {

        int x,y;

        scanf("%d%d",&x,&y);

        add(i,x,y);

    }

    dfs();

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

      change(in[i],,,n,),vis[i]=;

    scanf("%d",&m);

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

    {

        char c;int x;

        cin>>c;scanf("%d",&x);

        if(c=='Q')printf("%d\n",query(in[x],out[x],,n,));

        else

        {

            if(vis[x])

            {

                change(in[x],-,,n,);

                vis[x]=;

            }

            else

            {

                change(in[x],,,n,);

                vis[x]=;

            }

        }

    }

    return ;

}

巴特西

苹果树（codevs 1228）

最新文章

热门文章