pku3321 apple tree
为什么总是wa?树状数组貌似对啊var n,i,j,k,l:longint;
ss,sss:string;
ch:char;
f:array[1..100000] of boolean;
tree,be,en:array[1..100000] of longint;
a:array[1..100000,1..2] of longint;
procedure dfs(const x:longint);
var ii:longint;
begin
inc(l);
f[x]:=true;
be[x]:=l;
ii:=a[x,2];
while ii<>0 do
begin
if not f[ii] then dfs(ii);
ii:=a[ii,1];
end;
en[x]:=l;
end;
procedure change(const x,y:longint);
var ii:longint;
begin
ii:=x;
while ii<=n do
begin
inc(tree[ii],y);
ii:=ii+ii and -ii;
end;
end;
function sum(const x:longint):longint;
var ii,s:longint;
begin
ii:=x;
s:=0;
while ii>0 do
begin
inc(s,tree[ii]);
ii:=ii-ii and -ii;
end;
exit(s);
end;
begin
readln(n);
fillchar(a,sizeof(a),0);
for i:=1 to n-1 do
begin
readln(j,k);
if a[j,2]=0
then a[j,2]:=k
else begin
l:=a[j,2];
while a[l,1]<>0 do l:=a[l,1];
a[l,1]:=k;
end;
if a[k,2]=0
then a[k,2]:=j
else begin
l:=a[k,2];
while a[l,1]<>0 do l:=a[l,1];
a[l,1]:=j;
end;
end;
fillchar(f,sizeof(f),0);
l:=0;
dfs(1);
readln(n);
fillchar(f,sizeof(f),1);
for i:=1 to n do
begin
read(ch);
readln(j);
if ch='Q'
then writeln(en[j]-be[j]+1+sum(en[j])-sum(be[j]-1))
else begin
if f[j]
then change(be[j],-1)
else change(be[j],1);
f[j]:=not f[j];
end;
end;
end. 树状数组当然对。。写错了就是了 你看看哪写错了啊
貌似对啊 [code]
#include<cstdio>
#include<cstring>
const int mn=100010;
struct lnode
{
int v;
lnode *nxt;
}*g[mn],pg[mn*2];
int n,m,cnt,xx,ppg,ppt,a[mn],b[mn],s[2*mn];
bool h[mn],vis[mn];
char in[5];
void dfs(int v)
{
vis[v]=1;
a[v]=++cnt;
for(lnode *p=g[v];p;p=p->nxt)
if(!vis[p->v])dfs(p->v);
b[v]=++cnt;
}
void modify(int x,int k)
{
while(x<=cnt)s[x]+=k,x+=x&-x;
}
int query(int x)
{
if(!x)return 0;
int ret=0;
while(x>0)ret+=s[x],x-=x&-x;
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)
{
scanf("%d%d",&x,&y);
g[x]=&(pg[++ppg]=(lnode){y,g[x]});
g[y]=&(pg[++ppg]=(lnode){x,g[y]});
}
dfs(1);
memset(h+1,1,n);
scanf("%d",&m);
for(int i=1;i<=n;i++)modify(a[i],1);
while(m--)
{
scanf("%s%d",in,&xx);
if(in[0]=='C')
{
modify(a[xx],h[xx]?-1:1);
h[xx]=!h[xx];
}
else
printf("%d\n",query(b[xx])-query(a[xx]-1));
}
return 0;
}
[/code]
自己研究去吧 我的题解：
[url=http://fqq11679.blog.hexun.com/22987125_d.html]http://fqq11679.blog.hexun.com/22987125_d.html[/url]
这个题FDU貌似讲过，附上PPT一个。 奇怪,我方法对啊.............
还是wa.....................
郁闷............................
不做了.........................
页:
[1]