POJ 3321 Apple Tree(ツリー配列)
19917 ワード
标题:n個のリンゴが枝でつながっていて、これは1本の木です!C indとQ indの2つの操作があり、前者はindアップルを外し、もしなければ、新しい1つが生み出され、後者はindにいくつかの子アップルがあるかを調べる.
構想:第2の木の形の配列、自分で長い間どのように転化することを考えていないで、もとは木の性質を利用して、dfsは一回、各ノードのlowとhigh値を記録して、それでは彼の子の結点のlow値とhigh値はきっと[low,high]の間で、それからtre[high[i]-tre[low[i]-1]を通じて現在のノードの子の結点の個数を調べることができて、汗は1つ、自分のものじゃないし...
構想:第2の木の形の配列、自分で長い間どのように転化することを考えていないで、もとは木の性質を利用して、dfsは一回、各ノードのlowとhigh値を記録して、それでは彼の子の結点のlow値とhigh値はきっと[low,high]の間で、それからtre[high[i]-tre[low[i]-1]を通じて現在のノードの子の結点の個数を調べることができて、汗は1つ、自分のものじゃないし...
/*
Apple tree
* ， ， ，low[],high[]
* ， O(log(n))
*/
#include
<
iostream
>
#include
<
cstdio
>
#include
<
algorithm
>
#include
<
memory.h
>
#include
<
cmath
>
#include
<
bitset
>
#include
<
queue
>
#include
<
vector
>
using
namespace
std;
const
int
BORDER
=
(
1
<<
20
)
-
1
;
const
int
MAXSIZE
=
37
;
const
int
MAXN
=
202000
;
const
int
INF
=
1000000000
;
#define
CLR(x,y) memset(x,y,sizeof(x))
#define
ADD(x) x=((x+1)&BORDER)
#define
IN(x) scanf("%d",&x)
#define
OUT(x) printf("%d
",x)
#define
MIN(m,v) (m)<(v)?(m):(v)
#define
MAX(m,v) (m)>(v)?(m):(v)
#define
ABS(x) ((x)>0?(x):-(x))
typedef
struct
{
int
v,next;
}Edge;
Edge edge[MAXN
*
20
];
int
tre[MAXN],low[MAXN],net[MAXN],high[MAXN];
int
n_tre,n,cnt,index,m;
bool
visit[MAXN];
void
add_edge(
const
int
&
u,
const
int
&
v)
{
edge[index].v
=
v;
edge[index].next
=
net[u];
net[u]
=
index;
++
index;
edge[index].v
=
u;
edge[index].next
=
net[v];
net[v]
=
index;
++
index;
}
int
init()
{
cnt
=
0
;
index
=
0
;
CLR(tre,
0
);
CLR(visit,
0
);
CLR(net,
-
1
);
return
0
;
}
int
lowbit(
int
x)
{
return
x
&
(
-
x);
}
void
modify(
int
ind,
int
delta)
{
while
( ind
<=
n_tre)
{
tre[ind]
+=
delta;
ind
+=
lowbit(ind);
}
}
int
get_sum(
int
ind)
{
int
sum
=
0
;
while
(ind
>
0
)
{
sum
+=
tre[ind];
ind
-=
lowbit(ind);
}
return
sum;
}
int
input()
{
int
i,a,b;
for
(i
=
1
; i
<
n;
++
i)
{
scanf(
"
%d %d
"
,
&
a,
&
b);
add_edge(a,b);
}
return
0
;
}
void
dfs(
const
int
&
u)
{
++
cnt;
visit[u]
=
true
;
low[u]
=
cnt;
for
(
int
i
=
net[u]; i
!=
-
1
; i
=
edge[i].next)
if
(
!
visit[edge[i].v])
dfs(edge[i].v);
high[u]
=
cnt;
}
int
work()
{
int
i,j,tmp,ind;
int
ans;
char
c[
10
];
n_tre
=
n
<<
1
;
dfs(
1
);
IN(m);
CLR(visit,
0
);
for
(i
=
0
; i
<
m;
++
i)
{
scanf(
"
%s
"
,c);
scanf(
"
%d
"
,
&
ind);
if
(c[
0
]
==
'
Q
'
)
{
ans
=
high[ind]
-
low[ind]
+
1
+
get_sum(high[ind])
-
get_sum(low[ind]
-
1
);
OUT(ans);
}
else
{
if
(visit[ind])
modify(low[ind],
1
);
else
modify(low[ind],
-
1
);
visit[ind]
^=
1
;
}
}
return
0
;
}
int
main()
{
IN(n);
{
init();
input();
work();
}
return
0
;
}