欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

 

相关标签: codeforces