见标题. 树上带修莫队.

Table of Contents

  1. Description

Description

原题面太长了.

简单来说就是树上每个点有一个颜色, 有若干条路径的查询, 在这个路径上第$i$次碰到颜色$c$的收益是$v_c \times w_i$, 颜色可以修改.

经典的模板题.

我们要将树上莫队和带修莫队结合起来.

树上莫队有两种写法, 一种是用DFS序+栈, 不过没写过.

还有一种比较暴力, 用欧拉序, 这样可以直接消除对称差的影响.

关于对称差, 也就是如果$x, y$均不等于$LCA(x, y)$, 那么考虑一个去除$LCA$的询问,通过打$vis$标记统计贡献可以使得莫队的工作方式恰好得出正确的解, 我们最后把$LCA$的贡献考虑进去就可以了.

关于带修莫队, 就是按左端点所在块, 右端点所在块, 时间排序, 然后询问跑的同时维护一个修改指针, 视情况向前或回滚.

块大小是$N^{\frac{2}{3}}$.

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>

using namespace std;

typedef long long ll;

const int maxn = 1e+5 + 5;

int bel[maxn << 1], blo;
struct edge {
  int to, nxt;
}e[maxn << 1];
struct query
{
  int x, y, t, id;
  bool operator < (const query &rhs) const {
    return (bel[x] == bel[rhs.x]) ? ((bel[y] == bel[rhs.y]) ? t < rhs.t : bel[y] < bel[rhs.y]) : bel[x] < bel[rhs.x];
  }
}que[maxn], chg[maxn];
int n, m, q, in[maxn], out[maxn], cnt;
int ptr, lnk[maxn], lst[maxn], col[maxn], v[maxn];
int w[maxn];
int qptr, cptr;
int rev[maxn << 1], F[maxn][19], dep[maxn], inq[maxn];
int tim[maxn];
ll ans[maxn], global;

inline void add(int bgn, int end) {
  e[++ptr] = (edge){end, lnk[bgn]};
  lnk[bgn] = ptr;
}
void dfs(int x) {
  dep[x] = dep[F[x][0]] + 1;
  in[x] = ++cnt; rev[cnt] = x;
  for (int p = lnk[x]; p; p = e[p].nxt) {
    int y = e[p].to;
    if (y == F[x][0]) continue;
    F[y][0] = x; dfs(y);
  }
  out[x] = ++cnt; rev[cnt] = x;
}
void init() {
  for (int i = 1; i < 19; ++i) {
    for (int j = 1; j <= n; ++j) 
      F[j][i] = F[F[j][i - 1]][i - 1];
  }
}
inline int lca(int x, int y) {
  if (dep[x] > dep[y]) swap(x, y);
  for (int i = 18; ~i; --i)
    if (dep[F[y][i]] >= dep[x]) y = F[y][i];
  if (x == y) return x;
  for (int i = 18; ~i; --i)
    if (F[y][i] ^ F[x][i]) y = F[y][i], x = F[x][i];
  return F[x][0];
}
inline bool cmp(const query &lhs, const query &rhs) {
  return lhs.id < rhs.id;
}
inline void spot_modify(int node) {
  if (inq[node]) {
    global -= (ll)v[col[node]] * w[tim[col[node]]]; tim[col[node]]--;
  } else {
    tim[col[node]]++;
    global += (ll)v[col[node]] * w[tim[col[node]]];
  }
  inq[node] ^= 1;
}
inline void modify(int node, int ncol) {
  if (inq[node]) {
    spot_modify(node);
    col[node] = ncol;
    spot_modify(node);
  } else {
    col[node] = ncol;
  }
}

inline int rd() {
  register int x = 0, c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return x;
}

int main() {
  n = rd(); m = rd(); q = rd();
  for (int i = 1; i <= m; ++i) v[i] = rd();
  for (int i = 1; i <= n; ++i) w[i] = rd();
  int frm, to;
  for (int i = 1; i < n; ++i) {
    frm = rd(); to = rd();
    add(frm, to); add(to, frm);
  }
  dfs(1); init();
  blo = pow(cnt, 2 / 3.0) * 0.5;
  for (int i = 1; i <= cnt; ++i) bel[i] = (i - 1) / blo + 1;
  for (int i = 1; i <= n; ++i) lst[i] = col[i] = rd();
  int typ, x, y;
  for (int i = 1; i <= q; ++i) {
    typ = rd(); x = rd(); y = rd();
    if (!typ) {
      chg[++cptr] = (query){x, lst[x], y, 0};
      lst[x] = y;
    } else {
      ++qptr;
      if (in[x] > in[y]) swap(x, y); 
      int LCA = lca(x, y);
      que[qptr] = (query){LCA == x ? in[x] : out[x], in[y], cptr, qptr};
    }
  }
  sort(que + 1, que + 1 + qptr);
  int L = 1, R = 0, ptr = 1;
  for (int i = 1; i <= qptr; ++i) {
    while (ptr <= que[i].t) modify(chg[ptr].x, chg[ptr].t), ++ptr;
    while (ptr > que[i].t) modify(chg[ptr].x, chg[ptr].y), --ptr;
    while (L > que[i].x) spot_modify(rev[L - 1]), L--;
    while (L < que[i].x) spot_modify(rev[L]), L++;
    while (R > que[i].y) spot_modify(rev[R]), R--;
    while (R < que[i].y) spot_modify(rev[R + 1]), R++;
    int nodex = rev[que[i].x], nodey = rev[que[i].y], LCA = lca(nodex, nodey);
    if (nodex != LCA && nodey != LCA) {
      spot_modify(LCA);
      ans[que[i].id] = global;
      spot_modify(LCA);
    } else ans[que[i].id] = global;
  }
  //sort(que + 1, que + 1 + qptr, cmp);
  for (int i = 1; i <= qptr; ++i) printf("%lld\n", ans[i]);
  //printf("%lld\n", ans[que[i].id]);
  return 0;
}