2017-03-10

[WC 2013] 糖果公园

n个点的无根树, m种糖, 每个点有某种糖, 每种糖有权值d, 第i次吃某种糖有系数wi, 每次吃糖使愉悦指数增加权值x系数. q个操作, 每个操作修改某结点的糖的种类, 或者询问沿u到v的唯一路径一路吃过去的愉悦指数. (1≤di,wi≤10^6, wi是非递增序列, n,m,q≤10^5)

题面描述借鉴了一下cls的解题报告, "一路吃过去" 这个描述好可爱......可以在清橙上找到.

当年WC的题如今已成莫队裸题 QAQ 把树分块, 每个询问(u,v,t)以b[u]为第一关键字, b[v]为第二关键字, t (表示询问发生在修改0~t完成后) 为第三关键字排序, 跑个莫队, 然后此题就做完了. 也可以不跑莫队, 像区间众数一样预处理任意两块之间的答案, 这样就可以在线了, 但编码复杂度增加.

来证一证复杂度. 设每块的大小为b. 不考虑具体的分块方式, 但是假设前两维块内, 相邻两块之间转移的复杂度是. t的转移的复杂度为, 因为u, v所在的块有种组合方式, 每种组合内t不减. u, v转移的复杂度分为两个部分: 块内, 相邻两块之间. 前者发生的次数均为. 后者发生的次数取决于有多少种 "相邻两块". 于是, u的转移的复杂度为, v转移的复杂度为. 视n, q同阶, 运用均值不等值进行分析, 发现取是最优的. 总时间复杂度为.

顺便说说不带修改的序列上的莫队. 对于询问(l, r), 以l所在块的编号为第一关键字, 以r为第二关键字. r转移的复杂度为, l转移的复杂度为, 令, 总时间复杂度为. 如果把r的编号作为第二关键字呢? r的复杂度变为, 总时间复杂度的界是不变的.

把树分块的方式很多, 可以像 <王室联邦> 那样, 也可以直接在括号序列上搞 (问题简化为序列上的莫队算法).
直接给树分块的方法可见vFleaKing的题解. 在树上不是很好爬. 自己思考的时候发现lca那里不好处理 - 所以爬的时候就不要管lca了, 计算答案的时候单独考虑.
设S(x)为x到根的路径上点的集合. xor为集合的对称差运算 (异或). 设T(x,y)=S(x) xor S(y), 即x到y的路径上除去lca(x,y)的所有点的集合.
看一看T(x,y)怎么变到T(x,y').
T(x,y) = S(x) xor S(y) => S(x) = T(x,y) xor S(y) T(x,y') = S(x) xor S(y') 代入, 得 T(x,y') = T(x,y) xor S(y) xor S(y') = T(x,y) xor T(y,y')
也就是说, 将y到y'的路径上除了lca(y,y')的点的存在性取反.
用这种方式, 我们维护T, 再把lca处的答案加上. 找lca应当采取复杂度低于的算法.

在括号序列上搞写起来更简单, 同时常数更小.

规定一个点出现两次等同于未出现. 记点v的开始时间为st[v], 结束时间为ed[v], 则区间ed[u] ~ st[v] (设ed[u] ≤ st[v]) 包含了除lca(u,v)外的所有点.

刚看到这题的时候我的想法与之类似, 但是我想第一次+1, 第二次-1, 搞不成 QAQ 纠结了半天应该用欧拉序还是DFS序. 欧拉序不具备抵消这种良好的性质. 以为只有叶子结点有问题, 想把叶子复制两遍了事. 其实这是欧拉序的特性啦 - 有d个儿子, 则出现(d+1)次.

以下是在树上分块的版本的代码. 修改那里只有几行却漏洞百出 TAT 既然是修改, 赋值不能忘记. 只有点在我们所维护的集合里的时候, 才处理cnt.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
typedef long long ll;

const int MAX_N = 1e5, MAX_M = 1e5, MAX_Q = 1e5;

vector<int> adj[MAX_N + 1];
int n, fa[MAX_N + 1], dep[MAX_N + 1];

namespace LCA {
	int top[MAX_N + 1], son[MAX_N + 1];

	int dfs1(int u, int p)
	{
		fa[u] = p;
		int sz = 1, mx = 0;
		Rep (i, 0, adj[u].size()) {
			int v = adj[u][i];
			if (v != p) {
				dep[v] = dep[u] + 1;
				int s = dfs1(v, u);
				sz += s;
				if (s > mx) {
					son[u] = v;
					mx = s;
				}
			}
		}
		return sz;
	}

	void dfs2(int u, int t, int p)
	{
		top[u] = t;
		if (son[u])
			dfs2(son[u], t, u);
		Rep (i, 0, adj[u].size()) {
			int v = adj[u][i];
			if (v != p && v != son[u])
				dfs2(v, v, u);
		}
	}

	int lca(int u, int v)
	{
		while (top[u] != top[v]) {
			if (dep[top[v]] < dep[top[u]])
				u = fa[top[u]];
			else
				v = fa[top[v]];
		}
		return dep[v] < dep[u] ? v : u;
	}
}

using LCA::lca;

int b[MAX_N + 1];

namespace Block {
	int S[MAX_N], top, sz = 1, blk;

	int dfs(int u, int p)
	{
		int sum = 0;
		Rep (i, 0, adj[u].size()) {
			int v = adj[u][i];
			if (v != p) {
				sum += dfs(v, u);
				if (sum >= sz) {
					Rep (j, 0, sum)
						b[S[--top]] = blk;
					sum = 0;
					++blk;
				}
			}
		}
		S[top++] = u;
		return sum + 1;
	}

	void init()
	{
		ll nn = (ll)n * n;
		while ((ll)sz * sz * sz < nn) ++sz;
		dfs(1, 0);
		while (top)
			b[S[--top]] = blk-1;
	}
}

int cnt[MAX_M + 1], c[MAX_N + 1], w[MAX_N + 1], d[MAX_M + 1];
ll now, w_sum[MAX_N + 1];
bool e[MAX_N + 1];

namespace Xor {
	inline void vertex(int v)
	{
		int candy = c[v];
		now -= d[candy] * w_sum[cnt[candy]];
		cnt[candy] += e[v] ? -1 : 1;
		e[v] ^= 1;
		now += d[candy] * w_sum[cnt[candy]];
	}

	void path(int u, int v) // without lca(u, v)
	{
		if (dep[v] < dep[u]) swap(u, v);
		while (dep[v] > dep[u]) {
			vertex(v);
			v = fa[v];
		}
		while (u != v) {
			vertex(u);
			vertex(v);
			u = fa[u];
			v = fa[v];
		}
	}
}

struct Query {
	int k, u, v, t;
	bool operator<(const Query& o) const
	{
		return b[u] < b[o.u] || (b[u] == b[o.u] && b[v] < b[o.v])
			|| (b[u] == b[o.u] && b[v] == b[o.v] && t < o.t);
	}
} Q[MAX_Q];

struct Op {
	int v, x, y;
	void perform()
	{
		if (e[v]) {
			now += (ll)d[y] * w[cnt[y] + 1] - (ll)d[x] * w[cnt[x]];
			--cnt[x];
			++cnt[y];
		}
		c[v] = y;

	}

	void cancel()
	{
		c[v] = x;
		if (e[v]) {
			--cnt[y];
			++cnt[x];
			now -= (ll)d[y] * w[cnt[y] + 1] - (ll)d[x] * w[cnt[x]];
		}
	}
} O[MAX_Q];

int q_cnt, o_cnt;
ll ans[MAX_Q];

int main()
{
	int m, q;
	scanf("%d%d%d", &n, &m, &q);
	For (i, 1, m)
		scanf("%d", &d[i]);
	For (i, 1, n) {
		scanf("%d", &w[i]);
		w_sum[i] = w_sum[i-1] + w[i];
	}
	For (i, 1, n-1) {
		int a, b;
		scanf("%d%d", &a, &b);
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	For (i, 1, n)
		scanf("%d", &c[i]);
	Rep (i, 0, q) {
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		if (t) {
			Q[q_cnt] = (Query){q_cnt, x, y, o_cnt - 1};
			++q_cnt;
		} else if (c[x] != y) {
			O[o_cnt] = (Op){x, c[x], y};
			c[x] = y;
			++o_cnt;
		}
	}

	LCA::dfs1(1, 0);
	LCA::dfs2(1, 1, 0);
	Block::init();
	Rep (i, 0, q_cnt)
		if (b[Q[i].u] > b[Q[i].v]) swap(Q[i].u, Q[i].v);
	sort(Q, Q+q_cnt);

	Down (i, o_cnt-1, Q[0].t+1)
		c[O[i].v] = O[i].x;

	int u = Q[0].u, v = Q[0].u, t = Q[0].t;
	Rep (i, 0, q_cnt) {
		Xor::path(v, Q[i].v);
		Xor::path(u, Q[i].u);
		u = Q[i].u;
		v = Q[i].v;
		while (t < Q[i].t)
			O[++t].perform();
		while (t > Q[i].t)
			O[t--].cancel();
		int x = lca(u, v);
		ans[Q[i].k] = now + (ll)d[c[x]] * w[cnt[c[x]] + 1];
	}

	Rep (i, 0, q_cnt) printf("%lld\n", ans[i]);

	return 0;
}