用的是DFS序列+线段树的方法,找了数据在自己电脑上测AC,在这里测却只有40分,其余测试点全部是栈溢出,不知道是什么原因
这是代码,请大牛指教
{$inline on}
type
node=record
left,right,mid,size,count,lc,rc:longint;
edt:boolean;
end;
var
tree:array[1..262144] of node;
ed,next:array[1..200000] of longint;
head,bl,el:array[1..100000] of longint;
vst:array[1..100000] of boolean;
n,m,ec,cur,x,y,i:longint;
op:char;
procedure add_edge(const x,y:longint);inline;
begin
inc(ec);
ed[ec]:=y;
next[ec]:=head[x];
head[x]:=ec;
end;
procedure DFS(const u:longint);inline;
var
v,i:longint;
begin
vst[u]:=true;
inc(cur);
bl[u]:=cur;
i:=head[u];
while i<>0 do
begin
v:=ed[i];
if not(vst[v]) then DFS(v);
i:=next[i];
end;
el[u]:=cur;
end;
procedure push_down(const p:longint);inline;
begin
with tree[p] do
begin
if edt=false then exit;
if size>1 then
begin
with tree[lc] do
begin
count:=size-count;
edt:=not(edt);
end;
with tree[rc] do
begin
count:=size-count;
edt:=not(edt);
end;
end;
edt:=false;
end;
end;
procedure update(const p:longint);inline;
begin
with tree[p] do
begin
count:=tree[lc].count+tree[rc].count;
end;
end;
procedure build_tree(const p,l,r:longint);inline;
begin
with tree[p] do
begin
left:=l;
right:=r;
mid:=(l+r)>>1;
size:=r-l+1;
if size>1 then
begin
lc:=p<<1;
build_tree(lc,l,mid);
rc:=p<<1+1;
build_tree(rc,mid+1,r);
end;
end;
end;
procedure edit(const p,l,r:longint);inline;
begin
push_down(p);
with tree[p] do
begin
if (l<=left)and(r>=right) then
begin
count:=size-count;
edt:=not(edt);
exit;
end;
if l<=mid then
edit(lc,l,r);
if r>=mid+1 then
edit(rc,l,r);
end;
update(p);
end;
function query(const p,l,r:longint):longint;inline;
var
pt1,pt2:longint;
begin
push_down(p);
with tree[p] do
begin
if (l<=left)and(r>=right) then
exit(count);
pt1:=0;
pt2:=0;
if l<=mid then
pt1:=query(lc,l,r);
if r>=mid+1 then
pt2:=query(rc,l,r);
end;
update(p);
exit(pt1+pt2);
end;
begin
readln(n);
fillchar(head,sizeof(head),0);
ec:=0;
for i:=1 to n-1 do
begin
readln(x,y);
add_edge(x,y);
add_edge(y,x);
end;
fillchar(vst,sizeof(vst),false);
cur:=0;
DFS(1);
fillchar(tree,sizeof(tree),0);
build_tree(1,1,n);
readln(m);
for i:=1 to m do
begin
readln(op,x);
case op of
'C':edit(1,bl[x],el[x]);
'Q':writeln(query(1,bl[x],el[x]));
end;
end;
end.