首页 > 其他 > 详细

CF1076E Vasya and a Tree

时间:2018-11-16 21:59:39      阅读:151      评论:0      收藏:0      [点我收藏+]

题意

Here

思考

简要题意就是给定多个操作,每次操作将\(u\) 距离小于等于 \(k\) 且在 \(u\) 子树内的点点权值加 \(x\) ,输出最终各个点的权值。

看这题的时候我先想的是树剖,发现树剖并不好处理两点的距离限制

第二种想法是 \(bfs\) 序,想想可能不好处理(不考虑超时的话可以做,线段树维护 \(bfs\) 序,对于每一层我们知道节点编号的区间,然后每一层二分区间左右端点来判断是否在 \(u\) 的子树内,再更新,时间复杂度有、爆炸)

于是当时这题成功地没有做出来,我过于菜

考完看了看别人的代码...发现自己智障了...

考虑单独的一个节点 \(u\),它的操作影响的都是在它子树内的与 \(u\) 深度差小于等于 \(k\) 的节点,那么我们只要维护当前深度操作总和就行了(树状数组或线段树),但有一个问题,由于 \(u\) 点的操作只影响 \(u\) 的子树,其他节点怎么办 ? 我们可以先将所有操作离线,再总体按 \(dfs\) 实现:

  1. 进入该点
  2. 实现该点的所有操作
  3. 递归它的子树
  4. 撤销操作

这样 \(u\) 的操作就不会影响到其他子树上的点了,还有一个好处,我们并不需要修改深度 \(dep(u)\)~\(dep(u)+k\) 而只需修改 \(dep(k)\) 最后查询的时候查 \(sum(dep(u)\)~\(sum(max))\)就好,因为当查询到这个点时,只有 \(u\) 的祖先节点的操作实现了,那么对于任意的 \(u\) 的儿子节点,如果它的值有修改,说明这个修改操作是来自 \(u\) 的祖先节点的,所以 \(u\) 肯定也会被修改

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x * f;
}
const ll N = 300030;
struct node{
    ll nxt, to;
}edge[N << 1];
ll head[N], num;
void build(ll from, ll to){
    edge[++num].nxt = head[from];
    edge[num].to = to;
    head[from] = num;
}
ll c[N], n, m;
ll lowbit(ll x){ return x & -x; }
void add(ll pos, ll v){
    for(ll i=pos; i<=n; i+=lowbit(i)) c[i] += v;
}
ll query(ll pos){
    ll ans = 0;
    for(ll i=pos; i; i-=lowbit(i)) ans += c[i];
    return ans;
}
vector<ll> val[N], D[N];
ll ans[N];
void dfs(ll u, ll f, ll d){
    for(ll i=0; i<D[u].size(); i++){
        add(min(n, D[u][i] + d), val[u][i]);
    }
    ans[u] = query(n) - query(d - 1);
    for(ll i=head[u]; i; i=edge[i].nxt){
        ll v = edge[i].to;
        if(v == f) continue;
        dfs(v, u, d + 1);
    }
    for(ll i=0; i<D[u].size(); i++){
        add(min(n, D[u][i] + d), -val[u][i]);
    }
}
int main(){
    n = read();
    for(ll i=1; i<=n-1; i++){
        ll u = read(), v = read();
        build(u, v); build(v, u);
    }
    m = read();
    for(ll i=1; i<=m; i++){
        ll u = read(), d = read(), v = read();
        D[u].push_back(d);
        val[u].push_back(v);
    }
    dfs(1, 0, 1);
    for(ll i=1; i<=n; i++){
        cout << ans[i] << " ";
    }
    return 0;
}

总结

注意题目性质,树上的技巧要多学习……

CF1076E Vasya and a Tree

原文:https://www.cnblogs.com/alecli/p/9971695.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!