代码
/*http://blog.csdn.net/jiangzh7
By Jiangzh*/
#include<cstdio>
const int N=100000+10;
#define data_up() if(val[p]==-1&&val[p<<1]==val[(p<<1)+1])val[p]=val[p<<1]
int n,q;
struct link{int y;link *next;}*head[N];
int L[N],R[N],tt=0;
bool hash[N];
int val[N*4];
int sum[N*4];
void inlink(int x,int y)
{
link *node=new link;
node->y=y;
node->next=head[x];
head[x]=node;
}
void read()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
inlink(u,v);
inlink(v,u);
}
}
void dfs(int x)
{
if(hash[x]) return; hash[x]=true;
tt++;L[x]=tt;
for(link *node=head[x];node;node=node->next) dfs(node->y);
R[x]=tt;
}
void data_down(int p)
{
if(val[p]!=-1)
{
val[p<<1]=val[(p<<1)+1]=val[p];
val[p]=-1;
}
}
void change(int p,int l,int r,int a,int b)
{
if(a<=l && b>=r)
{
if(val[p]!=-1)
{
if(val[p]==0)
{
val[p]=1;
sum[p]=r-l+1;
}
else if(val[p]==1)
{
val[p]=0;
sum[p]=0;
}
return;
}
}
int m=(l+r)>>1;
if(val[p]==1) {sum[p<<1]=m-l+1;sum[(p<<1)+1]=r-(m+1)+1;}
if(val[p]==0) {sum[p]=sum[p<<1]=sum[(p<<1)+1]=0;}
data_down(p);
if(a<=m) change(p<<1,l,m,a,b);
if(b>m) change((p<<1)+1,m+1,r,a,b);
data_up();
sum[p]=sum[p<<1]+sum[(p<<1)+1];
}
int query(int p,int l,int r,int a,int b)
{
if(a<=l&&b>=r)
{
//if(val[p]==1) return r-l+1;
//if(val[p]==0) return 0;
return sum[p];
}
int m=(l+r)>>1,x1=0,x2=0;
if(val[p]==1) {sum[p<<1]=m-l+1;sum[(p<<1)+1]=r-(m+1)+1;}
if(val[p]==0) {sum[p]=sum[p<<1]=sum[(p<<1)+1]=0;}
data_down(p);
if(a<=m) x1=query(p<<1,l,m,a,b);
if(b>m) x2=query((p<<1)+1,m+1,r,a,b);
data_up();
sum[p]=sum[p<<1]+sum[(p<<1)+1];
return x1+x2;
}
void work()
{
dfs(1);
//for(int i=1;i<=n;i++) printf("%d ",L[i]);puts("");
//for(int i=1;i<=n;i++) printf("%d ",R[i]);puts("");puts("");puts("");
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
char op;int x;
scanf("\n%c%d",&op,&x);
if(op=='C') change(1,1,tt,L[x],R[x]);
else printf("%d\n",query(1,1,tt,L[x],R[x]));
//for(int i=1;i<=10;i++) printf("%d ",val[i]);puts("");
//for(int i=1;i<=10;i++) printf("%d ",sum[i]);puts("");puts("");
}
}
int main()
{
//freopen("chinese.in","r",stdin);
//freopen("chinese.out","w",stdout);
read();
work();
return 0;
}
状态: Unaccepted
测评机： Xeond[6]
得分： 40分
提交日期： 2013-3-3 9:19:00
有效耗时： 766毫秒
测试结果1: 通过本测试点|有效耗时109ms
测试结果2: 通过本测试点|有效耗时141ms
测试结果3: 通过本测试点|有效耗时406ms
测试结果4: 通过本测试点|有效耗时110ms
测试结果5: 选手程序运行超过时限
测试结果6: 选手程序运行超过时限
测试结果7: 选手程序运行超过时限
测试结果8: 选手程序运行超过时限
测试结果9: 选手程序运行超过时限
测试结果10: 选手程序运行超过时限