郑州网站推广公司价格,wordpress改模板,秀网站,河南安阳网站建设Apple Tree poj-3321 题目大意#xff1a;给你一个根固定的树#xff0c;每一个点的点权是0或1#xff0c;查询子树点权和。 注释#xff1a;$1\le n \le 10^5$。 想法#xff1a;刚刚学习dfs序#xff0c;刷到水题偶哈哈。 什么是dfs序#xff1f;就是在遍历树的时候记…Apple Tree poj-3321 题目大意给你一个根固定的树每一个点的点权是0或1查询子树点权和。 注释$1\le n \le 10^5$。 想法刚刚学习dfs序刷到水题偶哈哈。 什么是dfs序就是在遍历树的时候记录的每个点的出栈入栈序。这样就可以保证每一个节会出现两次且它的子树被其夹在中间。 然后子树信息就可以通过维护序列的鬼东西维护了qwq。 紧接着我们用树状数组维护被节点夹着的区间就是端点节点的子树用树状数组更新即可。 最后附上丑陋的代码... ... #include iostream
#include cstdio
#include cstring
#include algorithm
#define maxn 100010
using namespace std;
int tot,cnt;
int to[2*maxn],head[maxn],nxt[2*maxn];
int d[2*maxn];
int p1[maxn],p2[maxn];
int tree[4*maxn];
inline void add(int x,int y)
{to[tot]y;nxt[tot]head[x];head[x]tot;
}
int lowbit(int x)
{return x(-x);
}
void dfs(int pos,int fa)//初始构造dfs序
{d[cnt]1;p1[pos]cnt;for(int ihead[pos];i;inxt[i]){if(to[i]fa) continue;dfs(to[i],pos);}p2[pos]cnt;
}
void fix(int x,int ch)
{for(int ix;icnt;ilowbit(i)){tree[i]ch;}
}
int query(int x)
{int ans0;for(int ix;i;i-lowbit(i)){anstree[i];}return ans;
}
void original()
{cnttot0;memset(tree,0,sizeof tree);memset(head,0,sizeof head);
}
int main()
{int n,m;while(~scanf(%d,n)){original();for(int a,b,i1;in;i){scanf(%d%d,a,b);add(a,b);add(b,a);}dfs(1,0);for(int i1;in;i)//别忘了建树{fix(p1[i],1);}// for(int i1;icnt;i)// {// printf(%d ,query(i));// }// puts();char s[20];scanf(%d,m);for(int x,i1;im;i){scanf(%s,s1);if(s[1]C){scanf(%d,x);if(d[p1[x]]1) fix(p1[x],-1);else fix(p1[x],1);d[p1[x]]^1;}else{scanf(%d,x);printf(%d\n,query(p2[x])-query(p1[x]-1));}}}return 0;
}
// int main()
// {
// int n;
// scanf(%d,n);
// for(int a,b,i1;in;i)
// {
// scanf(%d%d,a,b);
// add(a,b);
// add(b,a);
// }
// dfs(1,0);
// for(int i1;icnt;i)
// {
// printf(%d ,d[i]);
// }
// puts();
// for(int i1;in;i)
// {
// printf(%d %d\n,p1[i],p2[i]);
// }
// return 0;
// }小结dfs序好东西好东西... ...转载于:https://www.cnblogs.com/ShuraK/p/8710605.html
