[BZOJ3052][UOJ#58][WC2013]糖果公园

[BZOJ3052][UOJ#58][WC2013]糖果公园

试题描述

Candyland 有一座糖果公园，公园里不仅有美丽的风景、好玩的游乐项目，还有许多免费糖果的发放点，这引来了许多贪吃的小朋友来糖果公园玩。

糖果公园的结构十分奇特，它由 n 个游览点构成，每个游览点都有一个糖果发放处，我们可以依次将游览点编号为 1 至 n。有 n−1 条双向道路连接着这些游览点，并且整个糖果公园都是连通的，即从任何一个游览点出发都可以通过这些道路到达公园里的所有其它游览点。

糖果公园所发放的糖果种类非常丰富，总共 m 种，它们的编号依次为 1 至 m。每一个糖果发放处都只发放某种特定的糖果，我们用 c 来表示 i 号游览点的糖果。

来到公园里游玩的游客都不喜欢走回头路，他们总是从某个特定的游览点出发前往另一个特定的游览点，并游览途中的景点，这条路线一定是唯一的。他们经过每个游览点，都可以品尝到一颗对应种类的糖果。

大家对不同类型的糖果的喜爱程度都不尽相同。根据游客们的反馈打分，我们得到了糖果的美味指数，第 i 种糖果的美味指数为 v。另外，如果一位游客反复地品尝同一种类的糖果，他肯定会觉得有一些腻。根据量化统计，我们得到了游客第 i 次品尝某类糖果的新奇指数 w，如果一位游客第 i 次品尝第 j 种糖果，那么他的愉悦指数 H 将会增加对应的美味指数与新奇指数的乘积，即 vw。这位游客游览公园的愉悦指数最终将是这些乘积的和。

当然，公园中每个糖果发放点所发放的糖果种类不一定是一成不变的。有时，一些糖果点所发放的糖果种类可能会更改（也只会是 m 种中的一种），这样的目的是能够让游客们总是感受到惊喜。

糖果公园的工作人员小 A 接到了一个任务，那就是根据公园最近的数据统计出每位游客游玩公园的愉悦指数。但数学不好的小 A 一看到密密麻麻的数字就觉得头晕，作为小 A 最好的朋友，你决定帮他一把。

输入

第一行包含三个正整数 n,m,q，分别表示游览点个数、糖果种类数和操作次数。

第二行包含 m 个正整数 v1,v2,…,vm。

第三行包含 n 个正整数 w1,w2,…,wn。

第四行到第 n+2 行，每行包含两个正整数 a,b，表示这两个游览点之间有路径可以直接到达。

第 n+3 行包含 n 个正整数 c,c,…,c。

接下来 q 行，每行包含三个整数 t,x,y，表示一次操作：

若 t 为 0，则 1≤x≤n，1≤y≤m，表示编号为 x 的游览点发放的糖果类型改为 y；

若 t 为 1，则 1≤x,y≤n，表示对出发点为 x，终止点为 y 的路线询问愉悦指数。

输出

按照输入的先后顺序，对于每个 t 为 1 的操作输出一行，用一个正整数表示答案。

输入示例

输出示例

数据规模及约定

对于所有的数据，1≤v,w≤10，1≤a,b≤n，1≤c≤m，w,w,…,w 是非递增序列，即对任意 1<i≤n，满足 w≤w。

题解

树上带修莫队，其实就是对树分块之后将每个询问 (u, v) 变成三元组 (u, v, t)（表示当前已经进行了前 t 个修改），然后按照 u 所在块为第一关键字，v 所在块为第二关键字，t 为第三关键字排序。接下来暴力做就好了。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <cmath>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

	if(Head == Tail) {

		int l = fread(buffer, 1, BufferSize, stdin);

		Tail = (Head = buffer) + l;

	}

	return *Head++;

}

int read() {

	int x = 0, f = 1; char c = Getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

	return x * f;

}

#define maxn 100010

#define maxm 200010

#define maxq 100010

#define maxlog 18

#define LL long long

int n, C, m, head[maxn], nxt[maxm], to[maxm], colv[maxn], timv[maxn], col[maxn];

void AddEdge(int a, int b) {

	to[++m] = b; nxt[m] = head[a]; head[a] = m;

	swap(a, b);

	to[++m] = b; nxt[m] = head[a]; head[a] = m;

	return ;

}

int Bsiz, S[maxn], top, cb, blid[maxn];

int fa[maxn], dep[maxn], clo, mnp[maxlog][maxn<<1], dfn[maxn];

void build(int u) {

	mnp[0][dfn[u] = ++clo] = u;

	int bot = top;

	for(int e = head[u]; e; e = nxt[e]) if(to[e] != fa[u]) {

		fa[to[e]] = u; dep[to[e]] = dep[u] + 1;

		build(to[e]);

		mnp[0][++clo] = u;

		if(top - bot >= Bsiz) {

			cb++;

			while(top > bot) blid[S[top--]] = cb;

		}

	}

	S[++top] = u;

	return ;

}

int Log[maxn<<1];

void rmq_init() {

	Log[1] = 0;

	for(int i = 2; i <= clo; i++) Log[i] = Log[i>>1] + 1;

	for(int j = 1; (1 << j) <= clo; j++)

		for(int i = 1; i + (1 << j) - 1 <= clo; i++) {

			int a = mnp[j-1][i], b = mnp[j-1][i+(1<<j-1)];

			mnp[j][i] = dep[a] < dep[b] ? a : b;

		}

	return ;

}

int lca(int a, int b) {

	int l = dfn[a], r = dfn[b];

	if(l > r) swap(l, r);

	int t = Log[r-l+1];

	a = mnp[t][l]; b = mnp[t][r-(1<<t)+1];

	return dep[a] < dep[b] ? a : b;

}

int q, cc, cq;

LL Ans[maxq];

struct Cmd {

	int id, col, clst;

	Cmd() {}

	Cmd(int _1, int _2, int _3): id(_1), col(_2), clst(_3) {}

} cs[maxq];

struct Que {

	int u, v, t, id;

	Que() {}

	Que(int _1, int _2, int _3, int _4): u(_1), v(_2), t(_3), id(_4) {}

	bool operator < (const Que& t) const {

		if(blid[u] != blid[t.u]) return blid[u] < blid[t.u];

		if(blid[v] != blid[t.v]) return blid[v] < blid[t.v];

		return this->t < t.t;

	}

} qs[maxq];

int U, V, T, tot[maxn];

LL ans;

bool tag[maxn];

void rev(int u) {

	if(tag[u]) ans -= (LL)timv[tot[col[u]]--] * colv[col[u]];

	else ans += (LL)timv[++tot[col[u]]] * colv[col[u]];

	tag[u] ^= 1;

	return ;

}

void change(int& node, int tar) {

	int c = lca(node, tar), To = tar;

	while(node != c) rev(node), node = fa[node];

	while(tar != c) rev(tar), tar = fa[tar];

	node = To;

	return ;

}

int main() {

	n = read(); C = read(); q = read();

	for(int i = 1; i <= C; i++) colv[i] = read();

	for(int i = 1; i <= n; i++) timv[i] = read();

	for(int i = 1; i < n; i++) {

		int a = read(), b = read();

		AddEdge(a, b);

	}

	for(int i = 1; i <= n; i++) col[i] = read();

	Bsiz = pow(n, 2.0 / 3);

	build(1);

	while(top) blid[S[top--]] = cb;

	rmq_init();

	for(int i = 1; i <= q; i++) {

		int tp = read();

		if(!tp) {

			int id = read(), co = read();

			cs[++cc] = Cmd(id, co, col[id]);

			col[id] = co;

		}

		else {

			int u = read(), v = read();

			cq++; qs[cq] = Que(u, v, cc, cq);

		}

	}

	for(int i = cc; i; i--) col[cs[i].id] = cs[i].clst;

	sort(qs + 1, qs + cq + 1);

	U = V = tot[col[1]] = tag[1] = 1; T = 0; ans = (LL)colv[col[1]] * timv[1];

	for(int i = 1; i <= cq; i++) {

		rev(lca(U, V)); rev(lca(qs[i].u, qs[i].v));

		change(U, qs[i].u);

		change(V, qs[i].v);

		while(T < qs[i].t) {

			T++;

			int u = cs[T].id;

			if(tag[u]) ans -= (LL)timv[tot[col[u]]--] * colv[col[u]];

			col[u] = cs[T].col;

			if(tag[u]) ans += (LL)timv[++tot[col[u]]] * colv[col[u]];

		}

		while(T > qs[i].t) {

			int u = cs[T].id;

			if(tag[u]) ans -= (LL)timv[tot[col[u]]--] * colv[col[u]];

			col[u] = cs[T].clst;

			if(tag[u]) ans += (LL)timv[++tot[col[u]]] * colv[col[u]];

			T--;

		}

		Ans[qs[i].id] = ans;

	}

	for(int i = 1; i <= cq; i++) printf("%lld\n", Ans[i]);

	return 0;

}