CodeForces - 1076E（树状数组+dfs+差分）

106 阅读 0 评论 70 点赞

我是靠谱客的博主殷勤汽车，这篇文章主要介绍CodeForces - 1076E（树状数组+dfs+差分），现在分享给大家，希望可以做个参考。

题目

从1开始dfs，如果遍历到当前点，说明这个点不会再被更新。
然后用树状数组，下标为这个点深度。
每次更新完回到当前点要还原回去，因为一点的两个孩子深度一样，但他们影响的节点是不一样的。

复制代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define LL long long
const int maxn = 3e5 + 10;
typedef pair<LL, LL>P;
struct node
{
int v, nxt;
}e[maxn << 1];
int head[maxn], cnt;
LL ans[maxn], tree[maxn];
void add(int u, int v)
{
e[++cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
LL lowbit(int x)
{
return x & (-x);
}
void update(int x, LL val)
{
while (x <= maxn)
{
tree[x] += val;
x += lowbit(x);
}
}
LL getsum(int x)
{
LL sum = 0;
while (x > 0)
{
sum += tree[x];
x -= lowbit(x);
}
return sum;
}
vector<P>vec[maxn];
void dfs(int u, int fa, int s)
{
for (int i = 0; i < vec[u].size(); i++)
{
int dep = vec[u][i].first;
int val = vec[u][i].second;
update(s, val);
update(s + dep + 1, -val);
}
ans[u] = getsum(s);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)continue;
dfs(v, u, s + 1);
}
for (int i = 0; i < vec[u].size(); i++)
{
int dep = vec[u][i].first;
int val = vec[u][i].second;
update(s,-val);
update(s + dep + 1, val);
}
}
int main()
{
int n, m;
scanf("%d", &n);
int u, v;
for (int i = 1; i < n; i++)
{
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
scanf("%d", &m);
LL dep, val;
while (m--)
{
scanf("%d%lld%lld", &u, &dep, &val);
vec[u].push_back({ dep,val });
}
dfs(1, 0, 1);
for (int i = 1; i <= n; i++)
{
printf("%lld ", ans[i]);
}
cout << endl;
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define LL long long
const int maxn = 3e5 + 10;
typedef pair<LL, LL>P;
struct node
{
int v, nxt;
}e[maxn << 1];
int head[maxn], cnt;
LL ans[maxn], tree[maxn];
void add(int u, int v)
{
e[++cnt].v = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
LL lowbit(int x)
{
return x & (-x);
}
void update(int x, LL val)
{
while (x <= maxn)
{
tree[x] += val;
x += lowbit(x);
}
}
LL getsum(int x)
{
LL sum = 0;
while (x > 0)
{
sum += tree[x];
x -= lowbit(x);
}
return sum;
}
vector<P>vec[maxn];
void dfs(int u, int fa, int s)
{
for (int i = 0; i < vec[u].size(); i++)
{
int dep = vec[u][i].first;
int val = vec[u][i].second;
update(s, val);
update(s + dep + 1, -val);
}
ans[u] = getsum(s);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v;
if (v == fa)continue;
dfs(v, u, s + 1);
}
for (int i = 0; i < vec[u].size(); i++)
{
int dep = vec[u][i].first;
int val = vec[u][i].second;
update(s,-val);
update(s + dep + 1, val);
}
}
int main()
{
int n, m;
scanf("%d", &n);
int u, v;
for (int i = 1; i < n; i++)
{
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
}
scanf("%d", &m);
LL dep, val;
while (m--)
{
scanf("%d%lld%lld", &u, &dep, &val);
vec[u].push_back({ dep,val });
}
dfs(1, 0, 1);
for (int i = 1; i <= n; i++)
{
printf("%lld ", ans[i]);
}
cout << endl;
return 0;
}