nefu 1330 树上计算 (dfs序+树状数组)

本文主要是介绍nefu 1330 树上计算 (dfs序+树状数组)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出一棵以 1 为根的树，初始每个顶点的权值为 0 。
现有两种操作: 1 x 代表将顶点 x 的权值加一 2 x 询问顶点 x 的子树（包含x本身）的权值和是多少

第一行样例个数 T （T<=10）
对于每组样例
第一行是一个数 N 代表顶点的个数（1 <= N <= 4e4）
随后 N - 1 行每行有两个数 x y 代表顶点 x y 由一条边相连·
接下来一行是一个数 M 代表操作的次数（1<= M <=4e4）
最后 M 行,每行两个数 1 x 或 2 x 代表操作（1 <= x <= N）

每次询问输出答案，每个答案占一行。

10
9
1 2
1 3
2 4
2 5
3 6
6 8
6 7
8 9
9
2 1
1 3
2 6
1 6
1 3
2 1
2 8
1 2
2 1
9
1 2
1 3
2 4
2 5
3 6
3 7
6 8
6 9
5
1 6
2 8
1 3
1 4
2 1

0
0
3
0
4
0
3

DT2131

中文题。

思路：

先用dfs求出他们的dfs序，ls到rs是他们的子树包括他们自己本身。这样我们就掌握了每个节点他们的子树是什么了。我们只需要一个能单点更新和区间查询的数据结构就行了。树状数组比较好写，我们就用树状数组来完成这件事。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=4e4+500;
int ls[maxn],rs[maxn];
vector<int> v[maxn];
int cnt;
int tr[maxn];
int lowbit(int i)
{return i&(-i);
}
void update(int i,int n,int c)
{while(i<=n){tr[i]+=c;i+=lowbit(i);}
}
int query(int n)
{int sum=0;while(n>0){sum+=tr[n];n-=lowbit(n);}return sum;
}
void dfs(int now,int fa)
{ls[now]=++cnt;for(int i=0;i<v[now].size();i++){if(v[now][i]==fa)continue;dfs(v[now][i],now);}rs[now]=cnt;
}
int main()
{int t,n,x,y,m,o;scanf("%d",&t);while(t--){memset(tr,0,sizeof(tr));scanf("%d",&n);cnt=0;for(int i=1;i<=n;i++)v[i].clear();for(int i=1;i<n;i++){scanf("%d%d",&x,&y);v[x].push_back(y);v[y].push_back(x);}dfs(1,0);scanf("%d",&m);for(int i=1;i<=m;i++){scanf("%d%d",&o,&x);if(o==1){update(ls[x],n,1);}else{printf("%d\n",query(rs[x])-query(ls[x]-1));}}}return 0;
}

这篇关于nefu 1330 树上计算 (dfs序+树状数组)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！