Educational Codeforces Round 138 F Distance to the Path

Distance to the Path

思维 + 树链剖分

• 首先与树链剖分无关，先考虑如果只更新一个点的情况

因为更新一个点，它既能向根的方向更新，又能向子树方向更新，非常难维护，于是我们只考虑维护一个节点的子树结点的增值

设数组 \(sum[i][j]\) 为与 \(j\) 结点距离为 \(i\) 的 \(j\) 的子树节点（子树的那一层节点）应当加上多少

1. 询问：这样询问一个点的值的计算方式就为 \(\sum_{0}^{d}(sum[i][fa_i[j]])\), \(fa_i[j]\) 表示 \(j\) 的第 \(i\) 级祖先，\(0\) 的话就是自己，\(1\) 就是父亲节点

2. 更新：对于当前点 \(i\) 来说，更新 \(sum[d][i]\) 和 \(sum[d – 1][i]\)；然后跳转到父节点，并且 \(d = d – 1\)，重复上述过程

对于这个更新，其实要画个图之后理解会更好，就每个结点负责增加两层，一层是因为下一次往父节点走了一步，另一层是因为 \(d – 1\)

如果上面的部分能理解清楚，这题就没啥难度了

注意如果到了根节点的话就不能这样更新了，显然会重复计算，因为没有往父节点走，因此考虑直接给根节点上面加多 \(d\) 层节点就行了（我的代码没加，硬是 if-else 了很多东西，加了会好想很多；前排很多大哥的代码都加了）

• 然后是维护一个路径的增值，这里考虑用重链剖分

不难想到，对于路径上的非 \(LCA\) 结点 \(i\)，只需要维护让 sum[d][i] += k 即可，这个过程就重链剖分板子，把 \(sum\) 改成树状数组就可以了

\(LCA\) 结点直接按上面的方法更新就行

更改的复杂度 \(O(nlog^2n)\)

查询的复杂度 \(O(dlogn)\)

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
inline int lowbit(int x){return x & (-x);}

struct BIT
{
    int n;
    vector<ll>tr;
    BIT(){}
    void init(int _n)
    {
        n = _n;
        tr.resize(n + 1);
    }
    BIT(int _n){init(_n);}
    void add(int x, ll val)
    {
        while(x <= n)
        {
            tr[x] += val;
            x += lowbit(x);
        }
    }
    void add(int l, int r, ll val)
    {
        add(r + 1, -val);
        add(l, val);
    }
    ll query(int x)
    {
        ll ans = 0;
        while(x)
        {
            ans += tr[x];
            x -= lowbit(x);
        }
        return ans;
    }
};

int top[maxn], fa[maxn], dep[maxn], siz[maxn];
int hson[maxn], dfn[maxn], rnk[maxn], tp = 0;
vector<vector<int>>gra;

void dfs1(int now, int pre, int d)
{
    dep[now] = d;
    fa[now] = pre;
    hson[now] = -1;
    for(int nex : gra[now])
    {
        if(nex == fa[now]) continue;
        dfs1(nex, now, d + 1);
        siz[now] += siz[nex];
        if(hson[now] == -1 || siz[nex] > siz[hson[now]]) hson[now] = nex;
    }
}

void dfs2(int now, int t)
{
    dfn[now] = ++tp;
    rnk[tp] = now;
    top[now] = t;
    if(hson[now] != -1)
    {
        dfs2(hson[now], t);
        for(int nex : gra[now])
        {
            if(nex == hson[now] || nex == fa[now]) continue;
            dfs2(nex, nex);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    gra.resize(n + 1);
    for(int i=1; i<n; i++)
    {
        int a, b;
        cin >> a >> b;
        gra[a].push_back(b);
        gra[b].push_back(a);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    vector<BIT>bit(21, BIT(n));
    int m;
    cin >> m;
    while(m--)
    {
        int op;
        cin >> op;
        if(op == 1)
        {
            int v;
            cin >> v;
            ll ans = 0;
            for(int i=0; i<=20 && v; i++, v=fa[v])
                ans += bit[i].query(dfn[v]);
            cout << ans << "\n";
        }
        else
        {
            int u, v, k, d;
            cin >> u >> v >> k >> d;
            while(top[u] != top[v])
            {
                if(dep[top[u]] < dep[top[v]]) swap(u, v);
                bit[d].add(dfn[top[u]], dfn[u], k);
                u = fa[top[u]];
            }
            if(dep[u] > dep[v]) swap(u, v);
            if(u != v) bit[d].add(dfn[hson[u]], dfn[v], k);
            while(1 != u && d)
            {
                bit[d].add(dfn[u], dfn[u], k);
                bit[d - 1].add(dfn[u], dfn[u], k);
                d--;
                u = fa[u];
            }
            if(d == 0) bit[0].add(dfn[u], dfn[u], k);
            else for(int i=0; i<=d; i++) bit[i].add(1, 1, k);
        }
    }
    cout << endl;
    return 0;
}

原文地址：http://www.cnblogs.com/dgsvygd/p/16834465.html