DDOSvoid's Blog

2022杭电多校1 G Treasure

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

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=7144

简要题意：给定一个 $n$ 个点 $m$ 条边的无向带权图，每个点有一个颜色 $c_i$ 和一个权值 $a_i$，现在有 $q$ 次操作，操作有两种，第一种是给定一个点 $x$ 和 $y$，将 $a_x$ 加上 $y$；第二种操作是给定一个点 $x$ 和 $y$，问从 $x$ 出发，每次只能走权值小于等于 $y$ 的边，能够到达的所有点中，对于每个颜色只取权值最大的点的权值的权值和是多少，题目保证每种颜色的点的个数不超过 $10$

$n,m,q\le 10^5$

Solution

首先我们考虑建出 $kruskal$ 重构树，那么每次询问相当于子树查询，但是对于每种颜色，我们只取权值最大的那个

因为每种颜色的点的数量很少，我们考虑对于每种颜色的点建一个虚树，维护子树内最大值的和，做一些链加，保证每个点的子树查询都只会查询到的最大值即可，这里的修改可以用树状数组实现

时间复杂度 $O(10n\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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#define maxn 100010
#define Maxn 200010
#define maxm 200010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

int n, m, q, c[maxn]; 
vector<int> A[maxn];
ll s[Maxn];

struct node {
    int fr, to, w;

    friend bool operator < (const node &u, const node &v) { return u.w < v.w; }
} E[maxm];

int fa[Maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

#define lc T[u].ch[0]
#define rc T[u].ch[1]
struct Tree {
    int v, ch[2];
} T[Maxn]; int top, rt;
inline void init_tree(int n) {
    for (int i = 1; i <= top; ++i)
        T[i].v = T[i].ch[0] = T[i].ch[1] = 0; 
    top = n; rt = 2 * n - 1;
}

int dep[Maxn], f[Maxn][21], in[Maxn], out[Maxn], c2;
void pre(int u, int fa, int d) {
    if (!u) return ;
    dep[u] = d; f[u][0] = fa; in[u] = ++c2;
    pre(lc, u, d + 1); pre(rc, u, d + 1);
    out[u] = c2;
}

void init_lca(int n) {
    for (int j = 1; j <= 20; ++j)
        for (int i = 1; i <= n; ++i) f[i][j] = f[f[i][j - 1]][j - 1];
}

int get_lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = 20; ~i; --i)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 20; ~i; --i)
        if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

ll Bit[Maxn];
void add(int i, ll v) { while (i <= top) Bit[i] += v, i += lowbit(i); }

ll get_sum(int i) {
    ll s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s; 
}

int id[Maxn];
struct xushu {
    static const int N = 25;
    
    struct Edge {
        int to, next;
    } e[N]; int c1, head[N];
    inline void add_edge(int u, int v) {
        e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
    }

    int a[N], bl[N];
    void solve(int col) {
        int n = 0, top = 1; c1 = 0;
        for (auto t : A[col]) a[++n] = t; 
        sort(a + 1, a + n + 1, [](const int &u, const int &v) { return in[u] < in[v]; });
        id[rt] = top; bl[top] = rt; 
        for (int i = 1; i <= n; ++i) id[a[i]] = ++top, bl[top] = a[i];
        for (int i = 1; i < N; ++i) head[i] = -1;
        stack<int> S; S.push(rt); 
        for (int o = 1, u = a[o]; o <= n; u = a[++o]) {
            if (u == rt) continue; int lca = get_lca(u, S.top());
            while (S.top() != lca) {
                int t = S.top(); S.pop();
                if (in[S.top()] < in[lca]) id[lca] = ++top, bl[top] = lca, S.push(lca);
                add_edge(id[S.top()], id[t]);
            } S.push(u);
        }
        while (S.top() != rt) {
            int t = S.top(); S.pop();
            add_edge(id[S.top()], id[t]);
        }
    }

    ll dfs(int u, int fa, int opt) {
        ll mx = s[bl[u]], sum = 0; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to; if (v == fa) continue;
            ll val = dfs(v, u, opt); mx = max(mx, val); sum += val;
        } add(in[bl[u]], opt * (mx - sum));
        return mx;
    }
} _T[maxn];
    
int jump(int x, int k) {
    for (int i = 20; ~i; --i)
        if (f[x][i] && T[f[x][i]].v <= k) x = f[x][i];
    return x; 
}

inline void solve_1() {
    int x, y; cin >> x >> y; 
    _T[c[x]].dfs(1, 0, -1); s[x] += y; _T[c[x]].dfs(1, 0, 1);
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    x = jump(x, y); 
    cout << get_sum(out[x]) - get_sum(in[x] - 1) << "\n";
}

void work() {
    cin >> n >> m >> q;

    c2 = 0; init_tree(n);
    for (int i = 1; i < 2 * n; ++i) Bit[i] = 0;
    for (int i = n + 1; i < 2 * n; ++i) s[i] = 0;
    for (int i = 1; i <= n; ++i) A[i].clear();
    
    for (int i = 1; i <= n; ++i) cin >> c[i], A[c[i]].push_back(i);
    for (int i = 1; i <= n; ++i) cin >> s[i];
    for (int i = 1; i <= m; ++i) cin >> E[i].fr >> E[i].to >> E[i].w;
    sort(E + 1, E + m + 1); init_fa(2 * n - 1); 
    for (int i = 1; i <= m; ++i) {
        int u = E[i].fr, v = E[i].to, w = E[i].w, fu, fv; 
        if ((fu = find(u)) == (fv = find(v))) continue;
        fa[fu] = fa[fv] = ++top; T[top].ch[0] = fu; T[top].ch[1] = fv; 
        T[top].v = w;
    } pre(rt, 0, 1); init_lca(top); 
    for (int i = 1; i <= n; ++i) {
        _T[i].solve(i);
        _T[i].dfs(1, 0, 1);
    } 
    for (int i = 1; i <= q; ++i) {
        int opt; cin >> opt;
        if (opt == 0) solve_1();
        else solve_2();
    }
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T; 
    while (T--) work(); 
    return 0;
}