题解 P11855 [CSP-J2022 山东] 部署

· · 题解

题解 P11855 [CSP-J2022 山东] 部署

前排提醒，本题解做法涉及以下知识点：

致管理：把时间算错了……只把“花絮”部分的“三年”改为“两年”，其他地方均未改动。

题意

给定一棵以 1 号点为根的树，初始时每个点有点权 a_i，维护 m 次操作，操作包括两种：

操作完后进行 q 次询问，每次指定一个点，询问其点权。

数据范围 1\le n,m,q\le 10^6,1\le a_i\le 10^9,1\le y\le 10。

思路

给的两种操作看上去不好下手，但是此题有一个令人注意的点：一般的题都是操作同时包括修改和查询，但本题中是修改完了再查询，这个时候就需要离线处理思想发挥作用了。所谓离线处理思想，就是在操作的时候不直接操作上去，而是把操作先记录下来，等到合适的时机（通常是用到的时候）再操作以优化复杂度。

读完这段话之后，如果你之前没有想到，建议先从这个入手继续思考一下，问题应该会简单很多。

这道题直接按照上面的说法做就可以了。开两个数组分别记录每个点 1 操作 y 值的和以及 2 操作 y 值的和。所有操作结束之后遍历整棵树，遍历到一个点时：

这样由于每条边最多会被遍历 3 次（该边的两个端点中，深度较小的点的两种操作均会遍历该边，深度较大的点的 2 操作遍历该边），故时间复杂度为 \text{O}(n)，然后直接回答询问即可。

代码

直接放上落满了灰的赛时代码，由于挺好写的，故没有注释。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,q,u,v,op,x,y,a[1000010],tag1[1000010],tag2[1000010],fa[1000010];
vector<ll> g[1000010];
void change(ll now){
    for(int i=0;i<g[now].size();i++){
        if(g[now][i]!=fa[now]){
            fa[g[now][i]]=now;
            change(g[now][i]);
        }
    }
}
void pushdown(ll now){
    a[now]+=tag1[now];
    a[now]+=tag2[now];
    for(int i=0;i<g[now].size();i++){
        a[g[now][i]]+=tag2[now];
        if(g[now][i]!=fa[now]){
            tag1[g[now][i]]+=tag1[now];
            pushdown(g[now][i]);
        }
    } 
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++){
        cin>>u>>v;
        u--;v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    fa[0]=0;
    change(0);
    cin>>m;
    while(m--){
        cin>>op>>x>>y;
        if(op==1)tag1[x-1]+=y;
        else tag2[x-1]+=y;
    }
    pushdown(0);
    cin>>q;
    while(q--){
        cin>>x;
        cout<<a[x-1]<<endl;
    } 
    return 0;
}

花絮

洛谷终于搬题了！

喜报：成功于近两年前准确预测了洛谷评定的题目难度。

本人场上获得了 290 分的好成绩，挂了 30 分，原因至今不明，合理怀疑是机子太慢了，因为我的 T3 在洛谷上怎么测都是 100 但官方测的是 70……

直观感受本套题目：