[WC2013]糖果公园-树上带修莫队

[WC2013]糖果公园

• 首先一遍dfs将树的括号序（DFS序）求出
• 将树上莫队改为序列上的操作
• 考虑到x-y的路径在dfs序上中间可能还会包含了x的子树
• 故我们可以将x-y的路径变为在dfs序上x一次出现位置到y第一次出现位置的区间
• 同时，我们要把在区间内出现两次的节点去除，故可用一个bool数组vis，统计当前是否计算了某一节点
• 最终，我们要判断特殊情况
• 1.如果x不为y的祖先，则x在区间内不会被计算（出现了两次）
• 2.如果lca不为x或y，则lca未被计算（出现零次）
• 然后就可以普通莫队做了
• 求LCA可以用树剖、倍增等，这里用了倍增

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;
const int LOG = 20;
int n, m, q, nl = 1, nr = 0, nt = 0;
long long vm[MAXN], wn[MAXN], a[MAXN], c[MAXN][2];
int block, B[MAXN];
int head[MAXN], nxt[MAXN << 1], v[MAXN << 1], cnt;
int qu, tx;
int dfn[MAXN], ind, fi[MAXN], se[MAXN];
int anc[MAXN][LOG], depth[MAXN];
int vis[MAXN];
int ct[MAXN];
long long res[MAXN], ans;
struct question
{
	int l, r, ti, id;
} ask[MAXN];
inline bool cmp(const question &a, const question &b)
{
	if(B[fi[a.l]] ^ B[fi[b.l]]) return B[fi[a.l]] < B[fi[b.l]];
	if(B[fi[a.r]] ^ B[fi[b.r]]) return B[fi[a.r]] < B[fi[b.r]];
	return a.ti < b.ti;
}
inline void add(int x, int y)
{
	nxt[++cnt] = head[x]; head[x] = cnt; v[cnt] = y;
	nxt[++cnt] = head[y]; head[y] = cnt; v[cnt] = x;
}
inline void dfsl(int u, int p, int d) 
{
    anc[u][0] = p; depth[u] = d;
    for (int i = head[u]; i; i = nxt[i]) 
    {
        if(v[i] == p) continue;
        dfsl(v[i], u, d + 1);
    }
}
inline void init() {
	dfsl(1, 0, 1);
	for (int j = 1; j < LOG; j++) 
		for (int i = 1; i <= n; i++) 
			anc[i][j] = anc[ anc[i][j - 1] ][j - 1];
}
inline void swim(int &x, int h) {
	for (int i = 0; h > 0; i++) 
	{
		if(h & 1) x = anc[x][i];
		h >>= 1;
	}
}
inline int LCA(int x, int y) 
{
	if(depth[x] < depth[y]) swap(x, y);
	if(y == 1) return 1;
	swim(x, depth[x] - depth[y]);
	if(x == y) return x;
	for (int i = LOG - 1; i >= 0; i--) 
	{
		if(anc[x][i] != anc[y][i]) 
		{
	   		x = anc[x][i];
	   		y = anc[y][i];
		}
	}
	return anc[x][0];
}
void dfs(int now, int f)
{
	dfn[++ind] = now; fi[now] = ind;
	for (int i = head[now]; i; i = nxt[i])
	{
		if(v[i] == f) continue;
		dfs(v[i], now);
	}
	dfn[++ind] = now; se[now] = ind;
}
inline void sol(int x)//原编号
{
	if(!vis[x]) ans += vm[a[x]] * wn[++ct[a[x]]];
	else ans -= vm[a[x]] * wn[ct[a[x]]--];
	vis[x] ^= 1;//翻转标记
}
void change()
{
	if(vis[c[nt][0]])
	{
		sol(c[nt][0]);
		swap(a[c[nt][0]], c[nt][1]);
		sol(c[nt][0]);
	}
	else swap(a[c[nt][0]], c[nt][1]);
}
int main()
{
	scanf("%d %d %d", &n, &m, &q);
	for (int i = 1; i <= m; i++) scanf("%lld", &vm[i]);
	for (int i = 1; i <= n; i++) scanf("%lld", &wn[i]);
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		add(x, y);
	}
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	init();
	dfs(1, 0);
	block = pow(ind, 2.0 / 3.0) + 1;
	for (int i = 1; i <= ind; i++) B[i] = (i - 1) / block + 1;
	tx = 0, qu = 0;
	for (int i = 1; i <= q; i++)
	{
		int opt; scanf("%d", &opt);
		if(opt == 0)
		{
			++tx;
			scanf("%lld %lld", &c[tx][0], &c[tx][1]);//0表示在原编号的位置，1表示修改的值
		}
		else 
		{
			++qu;
			scanf("%d %d", &ask[qu].l, &ask[qu].r);
			if(fi[ ask[qu].l ] > fi[ ask[qu].r ]) swap(ask[qu].l, ask[qu].r);
			ask[qu].id = qu; ask[qu].ti = tx;
		}
	}
	sort(ask + 1, ask + qu + 1, cmp);
	for (int i = 1; i <= qu; i++)
	{
		while(nl < fi[ask[i].l]) sol(dfn[nl++]);//dfn记录了原编号
		while(nl > fi[ask[i].l]) sol(dfn[--nl]);
		while(nr < fi[ask[i].r]) sol(dfn[++nr]);
		while(nr > fi[ask[i].r]) sol(dfn[nr--]);
		while(nt < ask[i].ti)
		{
			++nt;
   			//vis 记录一个 节点计算了几次
			change();
		}
		while(nt > ask[i].ti)
		{
			change();
			--nt;
		}
		int p = LCA(ask[i].l, ask[i].r);
		if(ask[i].l ^ p) sol(ask[i].l);
		if(ask[i].l ^ p && ask[i].r ^ p) sol(p);
		res[ask[i].id] = ans;
		if(ask[i].l ^ p) sol(ask[i].l);
		if(ask[i].l ^ p && ask[i].r ^ p) sol(p);
	}
	for (int i = 1; i <= qu; i++)
	{
		printf("%lld\n", res[i]);
	}
	return 0;
}

[WC2013]糖果公园-树上带修莫队

原文：https://www.cnblogs.com/hangzz/p/13257326.html