poj 3321 Apple Tree問題解

http://poj.org/problem?id=3321
それぞれの分岐点と末梢にはりんご(最大1個)がある可能性があります.毎回りんごを1つ外すことができます.あるいは、りんごが新しく生えてきて、いつでもある分岐点の上の子の木の中で、全部で何個のりんごがありますか.(分岐点数:100000)この問題はツリー配列で行うことができます.題意によると、最初はりんごができるところはすべてりんごがありました.
//木の配列/*1本の木にリンゴが生えています.各枝のノードにリンゴが生えている状態と生えていない状態の2つの操作があります.1つの操作は枝のリンゴの状態を変えることができます.もう1つの操作は、ある枝のノード以下のすべてのリンゴがどれだけあるかを尋ねます.具体的には、dfsを1回行い、各ノードの開始時間Start[i]と終了時間End[i]をメモすると、iノードのすべての子孫の開始時間と終了時間はStart[i]とEnd[i]の間にあり、ツリー配列CでStart[i]からEnd[i]の間の追加リンゴの総数を統計する必要があります.ここで木配列統計区間はSum(End[i])-Sum(Start[i]-1)で計算できる.*/
各ノードの最後の時間end[i]はこのノードを一意に表すことができるので、end[i]を使用してツリー配列の

#include
#include
#define MAX 100009

int G[MAX][100];
int num[MAX];
int c[2*MAX],start[MAX],end[MAX],ncnt=0;
bool flag[2*MAX];
void bfs(int pos){
	start[pos]=++ncnt;
	int len=num[pos];
	for(int i=0;i0){
		ret+=c[pos];
		pos-=lowbit(pos);
	}
	return ret;
}
int main(){
	int N,M;
	while(~scanf("%d",&N)){
		int a,b;
		memset(c,0,sizeof(c));
		memset(G,0,sizeof(G));
		memset(num,0,sizeof(num));
		memset(flag,false,sizeof(flag));
		for(int i=0;i

POJで、vectorでやり始めたところ、タイムアウト.
原因、詳細は以下を参照してください.http://blog.csdn.net/tyzhaoqi2004/article/details/6882660
北大合宿のテーマはこうです

#include 
#include 
using namespace std;
#define MY_MAX 220000
int C[MY_MAX];
typedef vector VCT_INT;
vector  G(MY_MAX/2); //   
int Lowbit[MY_MAX];
bool HasApple[MY_MAX/2];
int Start[MY_MAX]; //dfs      
int End[MY_MAX]; //dfs      
int nCount= 0;
void Dfs(int v)
{
    Start[v] = ++ nCount;
    for( int i= 0; i < G[v].size(); i++ )
        Dfs(G[v][i]);
    End[v] = ++ nCount;
}
int QuerySum(int p)
{
    int nSum = 0;
    while( p > 0 )
    {
        nSum += C[p];
        p -= Lowbit[p];
    }
    return nSum;
}
void Modify( int p,int val)
{
    while( p <= nCount )
    {
        C[p] += val;
        p += Lowbit[p];
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    int x,y;
    int i,j,k;
//  
    for( i= 0; i < n -1 ; i++ )
    {
        int a,b;
        scanf("%d%d",&a,&b);
        G[a].push_back(b); //a    b
    }
    nCount= 0;
    Dfs(1);
    for( i= 1; i <= nCount; i++)
    {
        Lowbit[i] = i& ( i^( i-1));
    }
    for( i= 1; i <= n; i++ )
        HasApple[i] = 1;
    int m;
// C  ，          
    for( i= 1; i <= nCount; i++ )
        C[i] = i-(i-Lowbit[i]);
// C[i] = Sum[i] -Sum[i-lowbit(i)]
    scanf("%d",&m);
    for( i= 0; i < m; i++ )
    {
        char cmd[10];
        int a;
        scanf("%s%d",cmd,&a);
        if( cmd[0] == 'C' )
        {
            if( HasApple[a] )
            {
                Modify( Start[a],-1);
                Modify( End[a],-1);
                HasApple[a] = 0;
            }
            else
            {
                Modify( Start[a],1);
                Modify( End[a],1);
                HasApple[a] = 1;
            }
        }
        else
        {
            int t1 = QuerySum(End[a]);
            int t2 = QuerySum(Start[a]-1);
            printf("%d
",(t1-t2)/2 );
        }
    }
}