DDOSvoid's Blog

CF 1749F Distance to the Path

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

题目描述

https://codeforces.com/contest/1749/problem/F

简要题意：给定一棵 $n$ 个点的无根树，现在有 $m$ 次操作，操作有两种，第一种操作给定 $x$，求 $x$ 的权值；第二种操作给定 $u,v,k,d$，将距离 $u$ 到 $v$ 的简单路径的距离小于等于 $d$ 的点的点权加上 $k$

$n,m\le 2\times 10^5,d\le 20$

Solution

我们首先考虑第二种操作改成将距离点 $u$ 小于等于 $d$ 的点权加上 $k$，由于 $d$ 很小，我们考虑将贡献按照子树的方式记录，即我们对于每个点记录 $f_{u,i}$ 表示 $u$ 的子树内距离 $u$ 为 $i$ 的点要加上 $f_{u,i}$，这样我们在查询的时候可以直接暴力前 $d$ 级祖先，然后我们修改时的做法大概是这样

1
2
3
4
5
6
void update(int x, int v) { 
	for (int i = d, t = x; ~i; t = fa[t], --i) {
        f[t][i] += v;
        if (i) f[t][i - 1] += v;
    }
}

对于路径，我们令 $lca$ 为 $u$ 和 $v$ 的 $lca$，我们只需要修改路径上所有点的 $f_{u,d}$ 以及 $f_{lca,d-1}$，然后我们将其看做 $fa_{lca}$ 的 $d-1$ 然后按照第一种做法即可，注意如果提前跳到根节点需要特判

时间复杂度 $O(n\log ^2n+dn\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <deque>
#include <vector>
#include <tuple>
#define maxn 200010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m; 

struct Fenwick_Tree {
    int Bit[maxn];

    void add(int i, int v) { while (i <= n) Bit[i] += v, i += lowbit(i); }
    int get_sum(int i) {
        int s = 0;
        while (i) s += Bit[i], i -= lowbit(i);
        return s;
    }
    void update(int x, int y, int v) { add(x, v), add(y + 1, -v); }
    int query(int x) { return get_sum(x); } 
} B[21];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dep[maxn], son[maxn], sz[maxn], f[maxn]; 
void dfs(int u, int fa) {
    int Max = 0; sz[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        f[v] = u; dep[v] = dep[u] + 1;
        dfs(v, u); sz[u] += sz[v];
        if (sz[v] > Max) Max = sz[v], son[u] = v;
    }
}

int top[maxn], id[maxn], bl[maxn];
void dfs(int u, int fa, int topf) {
    static int cnt = 0; 
    top[u] = topf; id[u] = ++cnt; bl[cnt] = u;
    if (son[u]) dfs(son[u], u, topf); 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        dfs(v, u, v);
    }
}

int update(int x, int y, int d, int v) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        B[d].update(id[top[x]], id[x], v);
        x = f[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    B[d].update(id[x], id[y], v);
    return x; 
}

inline void solve_1() {
    int x, ans = 0; cin >> x;
    for (int i = 0, t = x; i <= 20 && t; t = f[t], ++i)
        ans += B[i].query(id[t]);
    cout << ans << "\n";
}

inline void solve_2() {
    int x, y, v, d; cin >> x >> y >> v >> d;
    int lca = update(x, y, d, v); if (d) B[d - 1].update(id[lca], id[lca], v);
    for (int i = d - 1, t = lca; ~i; --i) {
        if (f[t]) {
            t = f[t];
            B[i].update(id[t], id[t], v);
            if (i) B[i - 1].update(id[t], id[t], v);
        } else {
            for (int j = i - 1; ~j; --j)
                B[j].update(id[t], id[t], v);
            break;
        }
    }
}

int main() { fill(head, head + maxn, -1);
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    } cin >> m; dep[1] = 1, dfs(1, 0), dfs(1, 0, 1);
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2();
    }
    return 0;
}