E. Vasya and a Tree (前缀和思维) Educational Codeforces Round 54 (Rated for Div. 2)
程序员文章站
2022-05-09 17:37:16
...
传送门:http://codeforces.com/problemset/problem/1076/E
题目大意:
一棵树,m次操作。每次操作将距离该点小于等于d的儿子点权加x,输出全部的点权。
题目思路:
首先离线查询,落实到每个点上,然后dfs的时候先把这些查询,加到差分的前缀和数组上,然后往下走的时候要加上相应的差分数组,同理回溯的时候要减去差分值,差分数组也要讲之前加的减去。复杂度O(n+m)
同时也可以树状数组维护前缀和,每个点单独查询。
差分数组做法:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN = 3e5+5;
vector<ll>v[MAXN];
struct node
{
ll d,x;
node(){}
node(ll a,ll b){
d = a;x = b;
}
}C[MAXN];
vector<node>g[MAXN];
ll sum[MAXN],ans[MAXN];
ll c[MAXN];
ll Max = 0;
void add(ll x,ll y)
{
for( ;x <= MAXN ;x += x&-x)
c[x] += y;
}
ll ask(ll x)
{
ll ans = 0 ;
for( ; x;x -= (x&-x))ans += c[x];
return ans;
}
ll as = 0;
void dfs(ll x,ll fa,ll dep)
{
ll len = v[x].size();
ll len2 = g[x].size();
for(ll i=0;i<len2;i++){
node to = g[x][i];
sum[dep] += to.x;
sum[min(Max+1,dep+to.d+1)] -= to.x;
}
as += sum[dep];
ans[x] = as;
for(ll i=0;i<len;i++){
ll to = v[x][i];
if(to == fa)continue;
dfs(to,x,dep+1);
}
as -= sum[dep];
for(ll i=0;i<len2;i++){
node to = g[x][i];
sum[dep] -= to.x;
sum[min(Max+1,dep+to.d+1)] += to.x;
}
}
void dfs_d(ll x,ll fa,ll dep)
{
Max = max(Max,dep);
ll len = v[x].size();
for(ll i=0;i<len;i++){
ll to = v[x][i];
if(to == fa)continue;
dfs_d(to,x,dep+1);
}
}
int main()
{
ll n;
scanf("%lld",&n);
for(ll i=1;i<n;i++){
ll a,b;
scanf("%lld%lld",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
ll m;
scanf("%lld",&m);
while(m--){
ll d,nd,x;
scanf("%lld%lld%lld",&nd,&d,&x);
g[nd].push_back(node(d,x));
}
dfs_d(1,1,1);
dfs(1,1,1);
for(ll i=1;i<=n;i++){
printf("%lld ",ans[i]);
}
printf("\n");
}
树状数组做法:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN = 3e5+5;
vector<ll>v[MAXN];
struct node
{
ll d,x;
node(){}
node(ll a,ll b){
d = a;x = b;
}
}C[MAXN];
vector<node>g[MAXN];
ll sum[MAXN],ans[MAXN];
ll c[MAXN];
void add(ll x,ll y)
{
for( ;x <= MAXN ;x += x&-x)
c[x] += y;
}
ll ask(ll x)
{
ll ans = 0 ;
for( ; x;x -= (x&-x))ans += c[x];
return ans;
}
void dfs(ll x,ll fa,ll dep)
{
ll len = v[x].size();
ll len2 = g[x].size();
for(ll i=0;i<len2;i++){
node to = g[x][i];
add(dep,to.x);
add(dep+to.d+1,-to.x);
}
ans[x] = ask(dep);
for(ll i=0;i<len;i++){
ll to = v[x][i];
if(to == fa)continue;
dfs(to,x,dep+1);
}
for(ll i=0;i<len2;i++){
node to = g[x][i];
add(dep,-to.x);
add(dep+to.d+1,to.x);
}
}
int main()
{
ll n;
scanf("%lld",&n);
for(ll i=1;i<n;i++){
ll a,b;
scanf("%lld%lld",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
ll m;
scanf("%lld",&m);
while(m--){
ll d,nd,x;
scanf("%lld%lld%lld",&nd,&d,&x);
g[nd].push_back(node(d,x));
}
dfs(1,1,1);
for(ll i=1;i<=n;i++){
printf("%lld ",ans[i]);
}
printf("\n");
}
上一篇: 爬虫-智联招聘
推荐阅读
-
Educational Codeforces Round 85 (Rated for Div. 2) C. Circle of Monsters(前缀和 预处理 贪心)
-
Educational Codeforces Round 67 (Rated for Div. 2) E. Tree Painting(树形dp)
-
Educational Codeforces Round 48 (Rated for Div. 2) C. Vasya And The Mushrooms(思维)
-
Educational Codeforces Round 50 (Rated for Div. 2) D. Vasya and Arrays(前缀和,思维)
-
E. Vasya and a Tree (前缀和思维) Educational Codeforces Round 54 (Rated for Div. 2)
-
Educational Codeforces Round 48 (Rated for Div. 2) D. Vasya And The Matrix(思维/构造)
-
Educational Codeforces Round 52 (Rated for Div. 2)B. Vasya and Isolated Vertices·「模拟,思维」