题解：CF1749F Distance to the Path

· · 题解

考虑如何去拆解一次修改操作。

对于一次 (u,v,k,d) 的修改，记 lca 为 u,v 的最近公共祖先，那么可以看到在 x 下方的一部分区域，被影响到的点的范围，大致是一层一层的。

如图，这里以 d=2，我们可以去大致观察这些层。

可以大致发现把被影响到的点里，深度相同的分到同一层里，然后要大致在 u,v,a,b,x 某个点的子树里。

记 V(u,d) 表示 u 子树内到 u 的距离为 d 的点集。可以发现其中的下面 4 层点其实分别就是 V(u,2),V(a,2),V(b,2),V(x,2)。

然后继续，我们可以知道上面 \{a,b,c,d\} 这一层点其实是 V(x,1)，\{x\} 是 V(x,0)。

那么，我们可以维护 V(u,d) 被修改的权值 f(u,d)，那么我们只需要对 (u,v) 这条链上的点整体做 f(i,d) 加 k 即可完成下面 4 色点的修改。链加的话，我们转为子树和，使用树状数组即可维护。

再看其它部分，也就是到子树内到 x 的距离 \le d，和子树外到 x 的距离 \le d 的点集。（虽然上面可以覆盖子树内到 x 的距离 =d 部分，但是我们还是把它放到这一部分来做）

记 x 的第 i 级祖先为 s_i。这里以 d=4 为例。

我们大致可以看到应该是 vsi 会影响 2 层，即 V(s_i,d-i),V(s_i,d-i-1)。原因就是 s_i 每次会上移一步，同时 v_i 内部需要被覆盖的节点到 v_i 的最大距离也会比 v_{i-1} 小一，整体来看 V(s_i,d-i) 的深度比 V(s_{i-1},d-(i-1)) 小 2。

当然，如果发现有些祖先不存在，比如 s_1=1，那么 s_2,s_3,s_4 就不存在，而我们似乎是要用到 s_2。假如 s_i=1，那么 V(s_i,d-i),V(s_i,d-i-1) 已经覆盖了，把剩下的 V(s_i,d-i-2),\dots,V(s_i,0) 在 s_i 处理掉即可。

这样，一次修改就是 O(\log n+d)。

一次查询的话，v 会属于 V(s_0,0),V(s_1,1),\dots,V(s_{20},20)，直接 O(d\log n) 统计即可。

总复杂度 O(qd\log n)。

:::info[Code]

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define LG(x) (31^__builtin_clz(x))
const int N=200005;
namespace Fastio{
    #define SIZIO (1<<22)
    #define gc() (rp1==rp2&&(rp2=(rp1=buf)+fread(buf,1,SIZIO,stdin))==rp1?EOF:*rp1++)
    char buf[SIZIO+1],*rp1,*rp2;
    inline int read(){
        int d=0,f=0;char ch=gc();
        while (!isdigit(ch)) f|=(ch=='-'),ch=gc();
        while (isdigit(ch)) d=(d<<1)+(d<<3)+ch-'0',ch=gc();
        return f?-d:d;
    }
};using namespace Fastio;
int n,h[N],dep[N],fa[20][N],e[N<<1],ne[N<<1],idx=1,bg[N],ed[N],tim,f[21][N];
inline void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u){
    bg[u]=++tim;
    for (int i=1;(1<<i)<=dep[u];i++) fa[i][u]=fa[i-1][fa[i-1][u]];
    for (int i=h[u],v;i;i=ne[i]) 
        if ((v=e[i])!=fa[0][u]) fa[0][v]=u,dep[v]=dep[u]+1,dfs(v);
    ed[u]=tim;
}
inline int LCA(int x,int y){
    if (dep[x]<dep[y]) swap(x,y);
    for (int i=LG(dep[x]+1);i>=0;i--)
        if (dep[x]-(1<<i)>=dep[y]) x=fa[i][x];
    if (x==y) return x;
    for (int i=LG(dep[x]+1);i>=0;i--)
        if (fa[i][x]!=fa[i][y]) x=fa[i][x],y=fa[i][y];
    return fa[0][x];
}
struct BIT{
    int t[N];
    inline void modify(int x,int v){for (int i=x;i<=n;i+=i&-i) t[i]+=v;}
    inline int query(int x) {int res=0;for (int i=x;i;i-=i&-i)res+=t[i];return res;}
    inline int query(int l,int r) {return query(r)-query(l-1);}
}tr[21];
signed main(){
    n=read();
    for (int i=1,u,v;i<n;i++) u=read(),v=read(),add(u,v),add(v,u);
    dfs(1);int m=read();
    while (m--){
        int op=read();
        if (op==1){
            ll ans=0;int v=read();
            for (int i=0;i<=20&&v;i++) 
                ans+=f[i][v]+tr[i].query(bg[v],ed[v]),v=fa[0][v];
            printf("%lld\n",ans);
        }
        else {
            int u=read(),v=read(),k=read(),d=read(),lca=LCA(u,v);
            tr[d].modify(bg[u],k),tr[d].modify(bg[v],k);
            tr[d].modify(bg[lca],-2*k);
            for (int i=0;i<=d&&lca;i++){
                f[d-i][lca]+=k;
                if (i<d) f[d-i-1][lca]+=k;
                if (lca==1){for (int j=d-i-2;j>=0;j--) f[j][lca]+=k;break;}
                lca=fa[0][lca];
            }
        }
    }
    return 0;
}

:::