CF1749F 题解

· · 题解

题意：

给定义一棵 n 个点的树，有两种操作。

1、查询 x 的权值。

2、给距离 (x, y) 这条链距离不超过 d 的点权加 k。

题解：

考虑一个点距离不超过 d。

那么它必然是子树内不超过 d 的，再加上子树外不超过 d 的。

注意到，若 x 不是链的 lca， 那么 fa[x] 必然也可以覆盖 x 子树外的部分。

所以说对于链上所有点 x，我们先只考虑其子树内距离为 d 的覆盖，可以用树状数组 + dfs 序完成。

那么再考虑从 lca 往上 d 步的这条链，相当于开始考虑 lca 其子树外的覆盖。

用 f[x][i] 表示 x 对子树内距离为 i 加的值，注意到，x 覆盖了距离不超过 d 的部分，那么 fa[x] 会将距离 x 为 d - 2 的部分多覆盖一次。

所以说容斥一下就好了。

时间复杂度 O(n \times (\log_2 n \times d + d \times d))。

代码：

#include <bits/stdc++.h>
#define ri register int
#define ll long long
using namespace std;
const int Maxn=2e5;
vector<int>adj[Maxn+5];
int f[Maxn+5][21];
int son[Maxn+5],size[Maxn+5],father[Maxn+5],top[Maxn+5],in[Maxn+5],out[Maxn+5],dep[Maxn+5],timer;
int n,m;
struct Fenwick {
    int c[Maxn+5];
    inline int lowbit(int x) {return x&(-x);}
    inline void add(int x,int d) {
        for(;x<=n;x+=lowbit(x))c[x]+=d;
    }
    inline int query(int x) {
        int res=0;
        for(;x>=1;x-=lowbit(x))res+=c[x];
        return res;
    }
    inline int rangequery(int l,int r) {
        return query(r)-query(l-1);
    }
}fen[21];
void dfs1(int u,int fa) {
    size[u]=1,father[u]=fa,dep[u]=dep[fa]+1;    
    int mx=0;
    for(ri v:adj[u]) 
        if(v!=fa) {
            dfs1(v,u);
            if(size[v]>mx)son[u]=v,mx=size[v];
            size[u]+=size[v];
        }
}
void dfs2(int u,int fa,int now) {
    top[u]=now,in[u]=++timer;
    if(son[u])dfs2(son[u],u,now);
    for(ri v:adj[u])
        if(v!=son[u]&&v!=fa)dfs2(v,u,v);
    out[u]=timer;
}
inline int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        x=father[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    return x;
}
inline void modify(int x,int y,int k,int d) {
    int z=lca(x,y);
    fen[k].add(in[x],d);
    fen[k].add(in[y],d);
    fen[k].add(in[z],-2*d);
    for(ri i=0;i<=k&&z;i++) {
        f[z][k-i]+=d;
        if(k-i-2>=0&&z!=1)f[z][k-i-2]-=d;
        z=father[z];
    }
}
inline int query(int x) {
    int res=0,dis=0;
    for(ri i=0;i<=20&&x;i++) {
        res+=fen[i].rangequery(in[x],out[x]);
        for(ri j=dis;j<=20;j++)res+=f[x][j];
        ++dis,x=father[x];
    }
    return res;
}
int main() {
    scanf("%d",&n);
    for(ri i=1;i<n;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs1(1,0),dfs2(1,0,1);
    scanf("%d",&m);
    while(m--) {
        int op;
        scanf("%d",&op);
        if(op==1) {
            int x;
            scanf("%d",&x);
            printf("%d\n",query(x));
        }
        else {
            int x,y,k,d;
            scanf("%d%d%d%d",&x,&y,&d,&k);
            modify(x,y,k,d);
        }
    }
    return 0;
}