Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

说下我的方法

Posted by yzhw at 2010-07-31 23:36:49 on Problem 3321
把树转换为后序序列,记录下每颗子树的开始位置和结束位置,恩,下面就是树状数组啦~贴代码

# include <cstdio>
# include <cstring>
using namespace std;
const int N=100005;
struct node
{
   int next;
   int v;
}branch[N];
int count=0;
int v[N];
int min(int a,int b)
{
    return a<b?a:b;
}
void insert(int v1,int v2)
{
   branch[count].next=v[v1];
   v[v1]=count;
   branch[count].v=v2;
   count++;
}
#define typev int                   // type of res 
int n;
typev ar[N];                        // index: 1 ~ N 
int lowb(int t) { return t & (-t) ; } 
void add(int i, typev v) { 
  for ( ; i <= n; ar[i] += v, i += lowb(i)); 
} 
typev sum(int i) { 
 typev s = 0; 
  for ( ; i > 0; s += ar[i], i -= lowb(i)); 
  return s; 
} 
int first[N],last[N];
int travel_last(int now)
{
   int p=v[now];
   int minnum=2*N;
   while(p!=-1)
   {
     minnum=min(travel_last(branch[p].v),minnum);
     p=branch[p].next;
   }
   count++;
   last[now]=count;
   minnum=min(minnum,count);
   first[now]=minnum;
   return minnum;
}

int main()
{
    scanf("%d",&n);
    memset(ar,0,sizeof(ar));
    for(int i=1;i<=n;i++)
       v[i]=first[i]=-1;
    for(int i=1;i<n;i++)
    {
      int v1,v2;
      scanf("%d %d",&v1,&v2);
      insert(v1,v2);
    }
    count=0;
    travel_last(1);
    for(int i=1;i<=n;i++)
      add(i,1);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
       char jud[3];
       int num;
       scanf("%s %d",jud,&num);
       if(jud[0]=='Q')
         printf("%d\n",sum(last[num])-sum(first[num]-1));
       else
       {
          if(sum(last[num])-sum(last[num]-1)==1)
             add(last[num],-1);
          else
             add(last[num],1);
       }
    }
    //system("pause");
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator