出题人题解||放松一下

T2_放松一下 题解

以下令 $opt=1$ 的事件为“操作 $1$”，$opt=2$ 的事件为“操作 $2$”。

测试点 $1\sim 2$

该特殊性质为得分型。

暴力即可。操作 $1$ 是 $O(1)$ 的，操作 $2$ 最坏情况下 $O(n)$，总时间复杂度 $O(qn)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
vector<int> g[500009];
int a[500009];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i = 1;i<=n;++i) cin>>a[i];
    for(int i = 1;i<n;++i){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    while(q--){
        int opt;
        cin>>opt;
        if(opt == 1){
            int x,y;
            cin>>x>>y;
            a[x] = y;
        }else{
            int x;
            cin>>x;
            int ans = 0;
            for(auto v:g[x]) ans+=a[v];//暴力寻找邻居节点求和
            ans+=a[x];
            cout<<ans<<'\n';
        }
    }
}

---

测试点 $3\sim 5$

该特殊性质为得分型。

由于没有修改操作，考虑对于每一条边计算贡献即可。

具体的，一条边 $u,v$ 给 $u$ 带来了 $a_v$ 的贡献，给 $v$ 带来了 $a_u$ 的贡献，加上这个点本身的贡献即为单次查询答案。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
int a[500009],ans[500009];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i = 1;i<=n;++i){
        cin>>a[i];
        ans[i]+=a[i];
    }
    for(int i = 1;i<n;++i){
        int u,v;
        cin>>u>>v;
        ans[u]+=a[v];//u-v连边，a[v]贡献给u,a[u]贡献给v
        ans[v]+=a[u];
    }
    while(q--){
        int opt,x;
        cin>>opt>>x;
        cout<<ans[x]<<'\n';
    }
}

时间复杂度：$O(q+n)$。

---

测试点 $6\sim 10$

由于该图实际上是一棵树，考虑把贡献拆开变成父亲的贡献加上自己和儿子的贡献。

那需要节点 $x$ 的父亲 $f_x$，然后维护 $x$ 和 $x$ 的直接子节点的总贡献 $s_x$。然后显然 $dfs$ 跑出 $f_x$ 和 $s_x$。

接着对应到两个操作：

• 操作 $1$：和点 $x$ 有关的是 $s_{f_x}$ 和 $s_x$。总贡献加上了 $y-a_x$。
• 操作 $2$：向上贡献即为 $a_{f_x}$，向下贡献为 $s_x$，总贡献为 $a_{f_x}+s_x$。

这样就做到了操作 $1,2$ 都是 $O(1)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
vector<int> g[500009];
int a[500009],s[500009],f[500009];
bool vis[500009];
void dfs(int u,int fa){
    vis[u] = 1;
    f[u] = fa;
    for(auto v:g[u]){
        if(!vis[v]&&v!=fa){
            dfs(v,u);
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i = 1;i<=n;++i) cin>>a[i];
    for(int i = 1;i<n;++i){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1,0);
    for(int i = 1;i<=n;++i){
        s[i]+=a[i];
        s[f[i]]+=a[i];
    }
    while(q--){
        int opt;
        cin>>opt;
        if(opt == 1){
            int x,y;
            cin>>x>>y;
            s[f[x]]+=y-a[x];
            s[x]+=y-a[x];
            a[x] = y;
        }else{
            int x;
            cin>>x;
            cout<<s[x]+a[f[x]]<<'\n';
        }
    }
}

时间复杂度：$O(q+n)$