BZOJ3052 [wc2013]糖果公园

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

思路比较简单，树上莫队。因为要修改，所以要把块的大小变成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", &amp;n, &amp;m, &amp;q);
bsz = (int)pow(n, 0.66) + 1;
for (int i = 1; i &lt;= m; ++ i)
	scanf(lld, v + i);
w[0] = 0;
for (int i = 1; i &lt;= n; ++ i) {
	scanf(lld, w + i);
	w[i] += w[i - 1];
}
memset(head, 0, sizeof(head));
for (int i = 1; i &lt; n; ++ i) {
	int u, v;
	scanf("%d%d", &amp;u, &amp;v);
	addEdge(u, v);
	addEdge(v, u);
}
for (int i = 1; i &lt;= n; ++ i)
	scanf("%d", ty + i);
divide();
tc = tq = 0;
for (int i = 0; i &lt; q; ++ i) {
	int t, a, b;
	scanf("%d%d%d", &amp;t, &amp;a, &amp;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 &gt; 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 &gt;= 0; -- i)
	ty[cg[i]. a] = cg[i]. pb;
cptMo();
for (int i = 0; i &lt; q; ++ i)
	if (ans[i] &gt; -1)
		printf(lld "\n", ans[i]);

}

Comments