POJ3321-Apple Tree(DFS序+线段树)

题目链接:POJ3321-Apple Tree

题意:

给定一棵树,树上最开始每个节点上都有1个果实。

然后有两种操作

  1. Q x:询问以x节点为根的树上共有多少果实。
  2. C x:改变节点C上的果实状态。

题解:

先利用DFS序,把树上的问题转化为线性问题。

然后记录in[x]和out[x]分别为节点x进入dfs序的时间戳和退出dfs序的时间戳,则显然区间[in[x],out[x]]的果实数量即为以x为根的树的所有果实;并且每次修改只需要修改in[x]这个点即为修改了节点x的状态。

显然,以上问题可以用线段树维护。

参考代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,m,tot=0,ans;
int a[100009],sum[100009*4],lazy[100009*4];
int dfsin[100009],dfsout[100009];
struct Edge
{
    int v,nxt;
} edge[200009];
int cnt=0,fir[100009];
void addedge(int u,int v)
{
    edge[cnt].v=v;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
bool used[100009];
void dfs(int u,int F)
{
    dfsin[u]=++tot;
    a[tot]=u;
    for(int i=fir[u];   i!=-1;  i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(used[v]||v==F)
            continue;
        used[v]=1;
        dfs(v,u);
    }
    dfsout[u]=tot;
}
void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void pushdown(int l,int r,int rt)
{
    if(lazy[rt])
    {

        lazy[rt<<1]=lazy[rt];
        lazy[rt<<1|1]=lazy[rt];
        //区间异或
        int mid=(l+r)>>1;
        sum[rt<<1]=(mid-l+1)-sum[rt<<1];
        sum[rt<<1|1]=(r-mid)-sum[rt<<1|1];
        lazy[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    lazy[rt]=0;
    if(l==r)
    {
        sum[rt]=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    pushup(rt);
}
void update(int L,int R,int val,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        lazy[rt]^=val;
        sum[rt]=r-l+1-sum[rt];
        return;
    }
    pushdown(l,r,rt);
    int mid=(l+r)>>1;
    if(L<=mid)
        update(L,R,val,l,mid,rt<<1);
    if(R>mid)
        update(L,R,val,mid+1,r,rt<<1|1);
    pushup(rt);
}
void query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
    {
        ans+=sum[rt];
        return;
    }
    pushdown(l,r,rt);
    int mid=(l+r)>>1;
    if(L<=mid)
        query(L,R,l,mid,rt<<1);
    if(R>mid)
        query(L,R,mid+1,r,rt<<1|1);
}

int main()
{
    scanf("%d",&n);
    memset(fir,-1,sizeof(fir));
    memset(used,0,sizeof(used));
    for(int i=1;    i<=n-1;   i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    dfs(1,-1);
    build(1,n,1);
    scanf("%d",&m);
    while(m--)
    {
        char op[5];
        int num;
        scanf("%s%d",op,&num);
        if(op[0]=='Q')
        {
            ans=0;
            query(dfsin[num],dfsout[num],1,n,1);
            printf("%d\n",ans);
        }
        else
        {
            update(dfsin[num],dfsin[num],1,1,n,1);
        }
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。