Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

树状数组 5272K 391MS

Posted by 322019281 at 2018-08-28 10:23:03 on Problem 3321
```#include<cstdio>
using namespace std;

const int N=100001,INF=2000000000;
struct edge
{
int v,next;
}e[N<<1];
bool vis[N];
char s[101];

int min(int a,int b)
{
if(a<b)return a;
return b;
}

{
while(x<=n)
{
c[x]+=v;
x+=x&-x;
}
}

void dfs(int u)
{
vis[u]=true;
int i,v;
{
v=e[i].v;
if(!vis[v])
{
dfs(v);
end[u]=min(end[u],end[v]);
}
}
id++;
pos[u]=id;
end[u]=min(end[u],id);
}

int sum(int x)
{
int res=0;
while(x)
{
res+=c[x];
x-=x&-x;
}
return res;
}

int main()
{
int m,i,tot=0,u,v,x;
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
tot++;
e[tot].v=v;
tot++;
e[tot].v=u;
end[i]=INF;
}
end[n]=INF;
dfs(1);
scanf("%d",&m);
while(m)
{
scanf("%s%d",s,&x);
if(s[0]=='Q')printf("%d\n",sum(pos[x])-sum(end[x]-1));
else
{
vis[x]=!vis[x];
}
m--;
}
return 0;
}```

Followed by: