UOJ 58 糖果公园
Problem :
给一棵n个点的树，每个点上有一种颜色，对于一条路径上的点，若 i 颜色第 j 次出现对该路径权值的贡献为 w[i] * c[j], 每次询问一条路径的权值，或者修改某个点的颜色。
Solution :
树上的带修改的莫队。
使用dfs序来对左右端点进行分块。
第一关键字分块排序左端点，第二关键字分块排序右端点，第三关键字排序询问顺序。
用S(v, u)代表 v到u的路径上的结点的集合。
用root来代表根结点，用lca(v, u)来代表v、u的最近公共祖先。
那么
S(v, u) = S(root, v) xor S(root, u) xor lca(v, u)
其中xor是集合的对称差。
简单来说就是节点出现两次消掉。
lca很讨厌，于是再定义
T(v, u) = S(root, v) xor S(root, u)
观察将curV移动到targetV前后T(curV, curU)变化：
T(curV, curU) = S(root, curV) xor S(root, curU)
T(targetV, curU) = S(root, targetV) xor S(root, curU)
取对称差：
T(curV, curU) xor T(targetV, curU)= (S(root, curV) xor S(root, curU)) xor (S(root, targetV) xor S(root, curU))
由于对称差的交换律、结合律：
T(curV, curU) xor T(targetV, curU)= S(root, curV) xor S(root, targetV)
两边同时xor T(curV, curU)：
T(targetV, curU)= T(curV, curU) xor S(root, curV) xor S(root, targetV)
发现最后两项很爽……哇哈哈
T(targetV, curU)= T(curV, curU) xor T(curV, targetV)
（有公式恐惧症的不要走啊 T_T）
也就是说，更新的时候，xor T(curV, targetV)就行了。
即，对curV到targetV路径(除开lca(curV, targetV))上的结点，将它们的存在性取反即可。
引用自vfk
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
const int N = 1000008;
int n, m, q, block_size, block_num;
vector <int> vec[N];
int cv[N], cw[N], cnt[N], a[N], b[N], vis[N];
int belong[N], num, tot1, tot2;
int fa[N][20], dep[N];
stack <int> st;
long long ans[N], sum;
struct query1
{
int u, v, ub, vb, x, id;
query1(){}
query1(int u, int v, int x, int id) : u(u), v(v), x(x), id(id)
{
ub = belong[u];
vb = belong[v];
}
bool operator < (const query1 &b) const
{
if (ub != b.ub) return ub < b.ub;
if (vb != b.vb) return vb < b.vb;
return x < b.x;
}
}q1[N];
struct query2
{
int pos, x, y;
query2(){}
query2(int pos, int x, int y) : pos(pos), x(x), y(y){}
}q2[N];
void stpop(int &num)
{
++block_num;
for (int i = 1; i <= num; ++i)
{
int p = st.top(); st.pop();
belong[p] = block_num;
}
num = 0;
}
int dfs(int u)
{
int num = 1;
st.push(u);
for (auto v : vec[u])
{
if (v == fa[u][0]) continue;
fa[v][0] = u; dep[v] = dep[u] + 1;
num += dfs(v);
if (num >= block_size) stpop(num);
}
return num;
}
int get_lca(int u, int v)
{
if (dep[u] < dep[v]) swap(u, v);
int d = dep[u] - dep[v];
for (int i = 19; i >= 0; --i)
if (d & (1 << i))
u = fa[u][i];
if (u == v) return u;
for (int i = 19; i >= 0; --i)
if (fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
return fa[u][0];
}
void init()
{
block_size = pow(n, 2.0 / 3); block_num = 0;
for (int i = 1; i <= m; ++i) cin >> cv[i];
for (int i = 1; i <= n; ++i) cin >> cw[i];
for (int i = 1; i <= n; ++i) vec[i].clear();
for (int i = 1; i < n; ++i)
{
int u, v; cin >> u >> v;
vec[u].push_back(v);
vec[v].push_back(u);
}
fa[1][0] = 0; dep[1] = 1;
int num = dfs(1);
if (num != 0) stpop(num);
assert(st.empty());
for (int i = 1; i < 20; ++i)
for (int j = 1; j <= n; ++j)
fa[j][i] = fa[fa[j][i - 1]][i - 1];
for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = a[i];
tot1 = tot2 = 0;
for (int i = 1; i <= q; ++i)
{
int t, x, y; cin >> t >> x >> y;
if (t == 0)
{
q2[++tot2] = query2(x, b[x], y);
b[x] = y;
}
else
{
++tot1;
q1[tot1] = query1(x, y, tot2, tot1);
}
}
sort(q1 + 1, q1 + tot1 + 1);
for (int i = 1; i <= n; ++i) vis[i] = 0;
for (int i = 1; i <= m; ++i) cnt[i] = 0;
}
void update(int pos)
{
if (vis[pos])
{
sum -= (long long)cw[cnt[a[pos]]] * cv[a[pos]];
cnt[a[pos]]--;
}
else
{
cnt[a[pos]]++;
sum += (long long)cw[cnt[a[pos]]] * cv[a[pos]];
}
vis[pos] ^= 1;
}
void change(int pos, int x)
{
if (vis[pos])
{
update(pos);
a[pos] = x;
update(pos);
}
else a[pos] = x;
}
void work(int u, int v)
{
int lca = get_lca(u, v);
while (u != lca)
{
update(u);
u = fa[u][0];
}
while (v != lca)
{
update(v);
v = fa[v][0];
}
}
void solve()
{
sum = 0;
for (int i = 1; i <= q1[1].x; ++i) change(q2[i].pos, q2[i].y);
work(q1[1].u, q1[1].v);
update(get_lca(q1[1].u, q1[1].v));
ans[q1[1].id] = sum;
update(get_lca(q1[1].u, q1[1].v));
for (int i = 2, u = q1[1].u, v = q1[1].v, x = q1[1].x; i <= tot1; u = q1[i].u, v = q1[i].v, x = q1[i].x, ++i)
{
for (int j = x + 1; j <= q1[i].x; ++j) change(q2[j].pos, q2[j].y);
for (int j = x; j >= q1[i].x + 1; --j) change(q2[j].pos, q2[j].x);
work(u, q1[i].u);
work(v, q1[i].v);
update(get_lca(q1[i].u, q1[i].v));
ans[q1[i].id] = sum;
update(get_lca(q1[i].u, q1[i].v));
}
for (int i = 1; i <= tot1; ++i) cout << ans[i] << endl;
}
int main()
{
cin.sync_with_stdio(0);
while (cin >> n >> m >> q)
{
init();
solve();
}
}