DLKKILL

DLKKILL's world

POJ - 3321 - Apple Tree (树状数组,DFS序,模板)

题目链接:POJ – 3321

题目大意:

有一颗树,根永远为1.

初始状态每个节点上的值都为1

有两种操作:

  1. 查询某一节点子树上所有节点和的值

  2. 将某一节点值取非

题目分析:

利用DFS序将树转变成线性区间结构,然后利用树状数组即可。

注意:莫名奇妙的卡vector,要用

  1. vector<vector<int> > a(N);  

而且不能用cin,cout才能过,不然TLE到死

给出代码:

#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int maxn=100000+10;
int lefts[maxn];
int rights[maxn];
int num[maxn];
int id;
int bit(int x)
{
    return (x&(-x));
}
vector<vector<int> > g(maxn);
void dfs(int root,int f)
{
    lefts[root]=id;
    for(int i=0; i<g[root].size(); i++)
    {
        int v=g[root][i];
        if(v==f)
            continue;
        id++;
        dfs(v,root);
    }
    rights[root]=id;
}
int sum[maxn];
void init()
{
    id=1;
    for(int i=0;i<maxn;i++)
        g[i].clear();
    memset(lefts,0,sizeof(lefts));
    memset(rights,0,sizeof(rights));
    memset(sum,0,sizeof(sum));
}
int n;
void change(int root,int d)
{
    int t=root;
    while(t<maxn)
    {
        sum[t]+=d;
        t+=bit(t);
    }
    return;
}
int get_sum(int root)
{
    int sums=0;
    while(root)
    {
        sums+=sum[root];
        root-=bit(root);
    }
    return sums;
}
int main()
{
   // ios::sync_with_stdio(false);
    while(~scanf("%d",&n))
    {
        init();
        for(int i=0; i<n-1; i++)
        {
            int a,b;
            //cin>>a>>b;
            scanf("%d%d",&a,&b);
            g[a].push_back(b);
            //g[b].push_back(a);
        }
        dfs(1,0);
        for(int i=1; i<=n; i++)
        {
            num[i]=1;
            change(i,1);
        }
        int T;
        cin>>T;
        //  cout<<T<<endl;
        while(T--)
        {
             char s[30];
             scanf("%s",s);
            //   cout<<"****"<<endl;
            if(s[0]=='Q')
            {
                int x;
                scanf("%d",&x);
                //    cout<<"**"<<endl;
                int ans=get_sum(rights[x])-get_sum(lefts[x]-1);
                printf("%d\n",ans);
            }
            else
            {
                int x;
                scanf("%d",&x);
                if(num[x])
                    change(lefts[x],-1);
                else
                    change(lefts[x],1);
                num[x]=!num[x];
            }
        }
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注