BZOJ3052 [wc2013]糖果公园

盯idy发现的题，之前想学然后放弃了，于是今天几乎写了一天。有种紧迫感啊。然后发现好多认识的人都是最近过的。

思路比较简单，树上莫队。因为要修改，所以要把块的大小变成n^2/3，然后用1086的方法分块。好像也可以直接按dfs序分块。两个端点和时间为三个关键字跑莫队。复杂度可以感受一下反正我也不会证。

要注意千万要控制LCA的用量，必需只能是O(n)级别的。在爬树的时候必需O(1)。我就是在移动时间的时候不小心手贱每次用一遍LCA，然后去检查在移动端点花了好久的时间。

比较不开心的是发现mac没法改栈空间？有两个点始终暴栈。而且拿另一台电脑的openSUSE跑，结果发现它的cpu没有mac好，跑得还比mac快！我猜是操作系统在捣鬼。mac还是比较坑啊不开心。然后在bzoj上跑的时间几乎是本地的5倍也是比较厉害啊。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 100009;
const int maxl = 19;

typedef struct node {
	int t;
	node *next;
} edge;
node nlst[maxn], *np(nlst);
struct chain {
	int sz;
	node *hd, *tl;
	chain() {
		hd = tl = 0;
		sz = 0;
	}
	inline void clear() {
		hd = tl = 0;
		sz = 0;
	}
	inline void push(int x) {
		np-> t = x;
		np-> next = 0;
		if (sz) {
			tl-> next = np;
			tl = np;
		}
		else {
			hd = np;
			tl = np;
		}
		++ np;
		++ sz;
	}
	inline void merge(chain a) {
		sz += a. sz;
		if (a. sz) {
			if (hd) {
				tl-> next = a. hd;
				tl = a. tl;
			}
			else {
				hd = a. hd;
				tl = a. tl;
			}
		}
	}
};
struct query {
	int a, b, i, pa, pb, pi;
};
inline bool operator <(const query& a, const query& b) {
	return (a. pa < b. pa) || (a. pa == b. pa && a. pb < b. pb) || (a. pa == b. pa && a. pb == b. pb && a. i < b. i);
}

typedef long long dint;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif

int n, m, q, tq, tc, ty[maxn], fb[maxn], tb, bsz;
int d[maxn], ath[maxn][maxl];
bool oc[maxn];
dint w[maxn], v[maxn], ans[maxn], cnt[maxn];
edge elst[maxn << 1], *ep(elst), *head[maxn];
query qr[maxn], cg[maxn];

inline void addEdge(int u, int v) {
	ep-> t = v;
	ep-> next = head[u];
	head[u] = ep ++;
}

chain dfs(int p) {
	chain w;
	for (int i = 1; i < maxl; ++ i)
		ath[p][i] = ath[ath[p][i - 1]][i - 1];
	for (edge* e = head[p]; e; e = e-> next)
		if (!d[e-> t]) {
			d[e-> t] = d[p] + 1;
			ath[e-> t][0] = p;
			chain g(dfs(e-> t));
			w. merge(g);
			if (w. sz >= bsz) {
				++ tb;
				for (node* it = w. hd; it; it = it-> next)
					fb[it-> t] = tb;
				w. clear();
			}
		}
	w. push(p);
	return w;
}
void divide() {
	memset(d, 0, sizeof(d));
	tb = 0;
	d[1] = 1;
	chain g(dfs(1));
	for (node* it = g. hd; it; it = it-> next)
		fb[it-> t] = tb;
}

int LCA(int u, int v) {
	if (d[u] < d[v])
		swap(u, v);
	for (int i = maxl - 1; i >= 0; -- i)
		if (d[ath[u][i]] >= d[v])
			u = ath[u][i];
	if (u == v)
		return u;
	for (int i = maxl - 1; i >= 0; -- i)
		if (ath[u][i] ^ ath[v][i]) {
			u = ath[u][i];
			v = ath[v][i];
		}
	return ath[u][0];
}
bool onChain(int u, int v, int p) {
	if (p == u || p == v)
		return 1;
	int a(LCA(u, v));
	if (p == a)
		return 1;
	if (LCA(p, a) != a)
		return 0;
	else
		return LCA(p, u) == p || LCA(p, v) == p;
}

inline void rmVertex(int p, dint& ans) {
	if (oc[p]) {
		ans -= w[cnt[ty[p]]] * v[ty[p]];
		-- cnt[ty[p]];
		ans += w[cnt[ty[p]]] * v[ty[p]];
		oc[p] = 0;
	}
}
inline void insVertex(int p, dint& ans) {
	if (!oc[p]) {
		ans -= w[cnt[ty[p]]] * v[ty[p]];
		++ cnt[ty[p]];
		ans += w[cnt[ty[p]]] * v[ty[p]];
		oc[p] = 1;
	}
}
void moveVertex(int& u, int v, int g, dint& ans) {
	int p(u), q(g), a(LCA(u, v)), t(LCA(a, g));
	if (t == a) {
		int x(LCA(u, g)), y(LCA(v, g));
		if (d[x] > d[y])
			t = x;
		else
			t = y;
		if (LCA(u, t) == t) {
			for (; q ^ t; q = ath[q][0])
				insVertex(q, ans);
			for (; p ^ t; p = ath[p][0])
				rmVertex(p, ans);
		}
		else {
			for (; q ^ t; q = ath[q][0])
				insVertex(q, ans);
			for (; p ^ a; p = ath[p][0])
				rmVertex(p, ans);
			rmVertex(a, ans);
			for (q = ath[t][0]; q ^ a; q = ath[q][0])
				rmVertex(q, ans);
		}
	}
	else {
		for (; p ^ a; p = ath[p][0])
			rmVertex(p, ans);
		for (p = ath[a][0]; p ^ t; p = ath[p][0])
			insVertex(p, ans);
		for (; q ^ t; q = ath[q][0])
			insVertex(q, ans);
		insVertex(t, ans);
	}
	u = g;
}

inline void chgType(int p, int tn, dint& ans) {
	if (oc[p]) {
		ans -= :: v[ty[p]] * w[cnt[ty[p]]];
		-- cnt[ty[p]];
		ans += :: v[ty[p]] * w[cnt[ty[p]]];
		ty[p] = tn;
		ans -= :: v[ty[p]] * w[cnt[ty[p]]];
		++ cnt[ty[p]];
		ans += :: v[ty[p]] * w[cnt[ty[p]]];
	}
	else {
		ty[p] = tn;
	}
}
void moveChgTime(int& t, int g, dint& ans) {
	for (; t + 1 < tc && cg[t + 1]. i < g; ++ t)
		chgType(cg[t + 1]. a, cg[t + 1]. b, ans);
	for (; t > -1 && cg[t]. i > g; -- t)
		chgType(cg[t]. a, cg[t]. pb, ans);
}

void cptMo() {
	memset(ans, -1, sizeof(ans));
	sort(qr, qr + tq);
	int u(1), v(1), t(-1);
	dint cans(:: v[ty[1]] * w[1]);
	memset(cnt, 0, sizeof(cnt));
	memset(oc, 0, sizeof(oc));
	oc[1] = 1;
	cnt[ty[1]] = 1;
	for (int i = 0; i < tq; ++ i) {
		moveVertex(u, v, qr[i]. a, cans);
		moveVertex(v, u, qr[i]. b, cans);
		moveChgTime(t, qr[i]. i, cans);
		ans[qr[i]. i] = cans;
	}
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	scanf("%d%d%d", &n, &m, &q);
	bsz = (int)pow(n, 0.66) + 1;
	for (int i = 1; i <= m; ++ i)
		scanf(lld, v + i);
	w[0] = 0;
	for (int i = 1; i <= n; ++ i) {
		scanf(lld, w + i);
		w[i] += w[i - 1];
	}
	memset(head, 0, sizeof(head));
	for (int i = 1; i < n; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		addEdge(u, v);
		addEdge(v, u);
	}
	for (int i = 1; i <= n; ++ i)
		scanf("%d", ty + i);
	divide();
	tc = tq = 0;
	for (int i = 0; i < q; ++ i) {
		int t, a, b;
		scanf("%d%d%d", &t, &a, &b);
		if (!t) {
			cg[tc]. i = i;
			cg[tc]. a = a;
			cg[tc]. b = b
			cg[tc]. pb = ty[a];
			ty[a] = b;
			++ tc;
		}
		else {
			if (a > b)
				swap(a, b);
			qr[tq]. i = i;
			qr[tq]. pi = i / bsz;
			qr[tq]. a = a;
			qr[tq]. pa = fb[a];
			qr[tq]. b = b;
			qr[tq]. pb = fb[b];
			++ tq;
		}
	}
	for (int i = tc - 1; i >= 0; -- i)
		ty[cg[i]. a] = cg[i]. pb;
	cptMo();
	for (int i = 0; i < q; ++ i)
		if (ans[i] > -1)
			printf(lld "\n", ans[i]);
}