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;
}

最后

以上就是殷勤汽车为你收集整理的CodeForces - 1076E（树状数组+dfs+差分）的全部内容，希望文章能够帮你解决CodeForces - 1076E（树状数组+dfs+差分）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。