AK-dream

【题目描述】

题目描述太长了。。。建议自行读题 传送门

题意:给你一棵树,每个点有一个颜色$c[x]$,每种颜色有一个权值$v[c]$,还有$n$个参数$w[i]$。

如果一条路径上颜色为$c$的点有$cnt$个,那么产生$v[c]*w[cnt]$的贡献,路径的总权值就是每种颜色产生的贡献和。

每次询问一条路径的权值或者更改一个点的颜色

【输入/输出格式】

不关心

题解

这道题就是树上莫队和带修莫队缝合在了一起。。。实际上,如果你两种都会的话,只需要稍微魔改一下代码,拼接在一起就可以了

如果不会的话请看这两篇模板题解:

树上莫队 带修莫队

一些细节:

带修莫队在更新修改操作的时候,不再是判断修改的那个点是不是在当前区间$[l,r]$内,而是直接判断那个点现在是否是选中的状态,即代码中的$vis[x]$

分块大小取$n^{\frac{2}{3}}$!!!

要开long long

代码

代码比较长 但是其实并不太难写

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
#include <bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;

template<typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

template<typename T>
inline void write(T x) {
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}

int n, m, Q, block, c[N], tmp[N];
int head[N], pre[N<<1], to[N<<1], sz;
int fa[N], son[N], rnk[N<<1], top[N], dfn[N], out[N], tme, siz[N], d[N];
ll val[N], w[N], ans[N];

inline void addedge(int u, int v) {
pre[++sz] = head[u]; head[u] = sz; to[sz] = v;
pre[++sz] = head[v]; head[v] = sz; to[sz] = u;
}

void dfs(int x) {
siz[x] = 1; dfn[x] = ++tme; rnk[tme] = x;
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (y == fa[x]) continue;
d[y] = d[x] + 1;
fa[y] = x;
dfs(y);
siz[x] += siz[y];
if (!son[x] || siz[son[x]] < siz[y]) son[x] = y;
}
out[x] = ++tme; rnk[tme] = x;
}

void dfs2(int x, int tp) {
top[x] = tp;
if (son[x]) dfs2(son[x], tp);
for (int i = head[x]; i; i = pre[i]) {
int y = to[i];
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}

inline int LCA(int x, int y) {
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
x = fa[top[x]];
}
if (d[x] > d[y]) swap(x, y);
return x;
}

struct query{
int l, r, t, lca, id;
friend bool operator < (query x, query y) {
if (x.l / block != y.l / block) return x.l < y.l;
else if (x.r / block != y.r / block) return x.r < y.r;
else return x.t < y.t;
}
} q[N];

struct modify{
int p, x, y;
} q2[N];

int qcnt, mcnt, nowl, nowr, nowt, cnt[N];
ll nowans;
bool vis[N];

inline void add(int col) {
nowans += val[col] * w[++cnt[col]];
}

inline void del(int col) {
nowans -= val[col] * w[cnt[col]--];
}

inline void calc(int x) {
if (!vis[x]) add(c[x]);
else del(c[x]);
vis[x] = !vis[x];
}

inline void updtime(int t, int v) {
if (v == 1) {
if (vis[q2[t].p]) {
del(q2[t].x); add(q2[t].y);
}
c[q2[t].p] = q2[t].y;
} else {
if (vis[q2[t].p]) {
del(q2[t].y); add(q2[t].x);
}
c[q2[t].p] = q2[t].x;
}
}

int main() {
read(n); read(m); read(Q);
block = pow(n, 0.6666666667);
for (int i = 1; i <= m; i++) read(val[i]);
for (int i = 1; i <= n; i++) read(w[i]);
for (int i = 1, u, v; i < n; i++) {
read(u); read(v);
addedge(u, v);
}
for (int i = 1; i <= n; i++) {
read(c[i]);
tmp[i] = c[i];
}
dfs(1); dfs2(1, 1);
for (int i = 1, tp, u, v; i <= Q; i++) {
read(tp); read(u); read(v);
if (!tp) {
q2[++mcnt] = {u, tmp[u], v};
tmp[u] = v;
} else {
if (dfn[u] > dfn[v]) swap(u, v);
int lca = LCA(u, v);
if (lca == u) {
q[++qcnt] = {dfn[u], dfn[v], mcnt, 0, qcnt};
} else {
q[++qcnt] = {out[u], dfn[v], mcnt, lca, qcnt};
}
}
}
nowl = 1, nowr = 0, nowt = 0;
sort(q + 1, q + qcnt + 1);
for (int i = 1; i <= qcnt; i++) {
while (nowl < q[i].l) calc(rnk[nowl++]);
while (nowl > q[i].l) calc(rnk[--nowl]);
while (nowr < q[i].r) calc(rnk[++nowr]);
while (nowr > q[i].r) calc(rnk[nowr--]);
if (q[i].lca) calc(q[i].lca);
while (nowt < q[i].t) updtime(++nowt, 1);
while (nowt > q[i].t) updtime(nowt--, -1);
ans[q[i].id] = nowans;
if (q[i].lca) calc(q[i].lca);
}
for (int i = 1; i <= qcnt; i++) {
write(ans[i]);
puts("");
}
return 0;
}

 评论