作者:木马 | 来源:互联网 | 2023-05-17 22:13
给定一棵树,树上权值初始时为1。给出两种操作:1.将单点权值取反。2.查询子树的权值和。我们可以通过dfs将其映射到一个树状数组里,记录子树的起始位置以及终止位置。直
给定一棵树,树上权值初始时为1。
给出两种操作:
1.将单点权值取反。
2.查询子树的权值和。
我们可以通过dfs将其映射到一个树状数组里,记录子树的起始位置以及终止位置。直接暴力改logn查询即可。
#include
#include
using namespace std;
const int Maxn=2e5+5;
int n,m,Timer=0,tot=0;
int c[Maxn],in[Maxn],out[Maxn],f[Maxn];
bool b[Maxn];
struct edge{
int nex,to;
}e[Maxn];
inline void add(int u,int v){
e[++tot]=(edge){f[u],v};
f[u]=tot;
}
void dfs(int x){
in[x]=++Timer;
for(int i=f[x];i;i=e[i].nex){
int v=e[i].to;
if(in[v]) continue;
dfs(v);
}
out[x]=Timer;
}
inline int lowbit(int x){return x&-x;}
void update(int x,int v){ for(;x<=n;x+=lowbit(x))c[x]+=v; }
int query(int x){int sum=0;for(;x;x-=lowbit(x))sum+=c[x];return sum;}
int main(){
scanf("%d",&n);
int u,v;
for(int i=1;i