糖果公园[WC2013]

【题目描述】

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

题意：给你一棵树，每个点有一个颜色\(c[x]\)，每种颜色有一个权值\(v[c]\)，还有\(n\)个参数\(w[i]\)。

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

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

【输入/输出格式】

不关心

题解

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

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

树上莫队 带修莫队

一些细节：

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

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

要开long long

代码

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

#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;
} 

糖果公园[WC2013]

原文：https://www.cnblogs.com/ak-dream/p/AK_DREAM74.html