【zzuliOJ】1916 - 树（dfs序 & 树状数组）

FishWang

发布于 2025-08-27 10:57:55

2200

点击打开题目

1916: 树

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 226 Solved: 19 Submit Status Web Board

Description

给一颗树,有n个结点,编号为1到n，1为根节点,有两种操作，1 x y把x结点权值加y,2 x查询x到根节点所有结点的权值和. 每个结点权值初始化为0。

Input

第一行输入一个整数t，代表有t组测试数据。每组数据第一行为两个整数n,m代表结点个数和操作次数。接下来n-1行，每行两个整数a,b，表示a结点和b结点有一条边。接下来m行每行一个操作格式如上。 0<=n<=50000 ,0<=m<=50000，0<=y<=50000

Output

对于每组查询输出一个整数表示结果

Sample Input

5 5

1 2

1 3

3 4

3 5

2 5

1 1 2

1 3 1

2 4

2 1

Sample Output

HINT

Source

haut

学习了，先记录树的dfs序。每个节点记录down和up两个值。

然后点更新的时候，down的位置加，up的位置减，用树状数组维护就行了。

代码如下：

#include <stdio.h>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define LL long long
#define MAX 50000
struct node
{
	int down,up;
}dot[MAX+5];
LL sum[MAX*2+5];		//int会WA 
int cnt;
int n;
vector<int> mapp[MAX+5];
void dfs(int root,int fa)
{
	dot[root].down = cnt++;
	for (int i = 0 ; i < mapp[root].size() ; i++)
	{
		int pos = mapp[root][i];
		if (pos != fa)
			dfs(pos,root);
	}
	dot[root].up = cnt++;
}
void add(int x,int y)
{
	while (x <= 2*n)
	{
		sum[x] += y;
		x += x & (-x);
	}
}
LL Query(int x)
{
	LL ans = 0;
	while (x)
	{
		ans += sum[x];
		x = x & (x-1);
	}
	return ans;
}
int main()
{
	int u;
	int k;
	int op,x,y;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d %d",&n,&k);
		for (int i = 1 ; i <= n ; i++)
			mapp[i].clear();
		for (int i = 1 ; i < n ; i++)
		{
			int t1,t2;
			scanf ("%d %d",&t1,&t2);
			mapp[t1].push_back(t2);
			mapp[t2].push_back(t1);
		}
		cnt = 1;
		dfs(1,0);  		//记录dfs序 
		CLR(sum,0);
		while (k--)
		{
			scanf ("%d %d",&op,&x);
			if (op == 1)
			{
				scanf ("%d",&y);
				add(dot[x].down,y);
				add(dot[x].up,-y);
			}
			else
				printf ("%lld\n",Query(dot[x].down));
		}
	}
	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs