BZOJ 3052/Luogu P4074 [wc2013]糖果公园（树上带修莫队）

题面

分析

树上带修莫队板子题。。。

开始没给分块大小赋初值T了好一会。。。

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template<typename T>inline void read(T &num) {

	char ch; while((ch=getchar())<'0'||ch>'9');

	for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());

}

const int MAXN = 100005;

int Block, n, m, q, V[MAXN], W[MAXN], a[MAXN], bel[MAXN], la[MAXN], val[MAXN];

LL ans[MAXN], Ans; bool vis[MAXN];

struct Change {

	int i, u, v;

}C[MAXN];

struct Query {

	int u, v, t, id;

	inline bool operator <(const Query &o)const {

		return bel[u] == bel[o.u] ? (bel[v] == bel[o.v] ? t < o.t : bel[v] < bel[o.v]) : bel[u] < bel[o.u];

	}

}Q[MAXN];

int fir[MAXN], to[MAXN<<1], nxt[MAXN<<1], cnt;

inline void add(int x, int y) { to[++cnt] = y; nxt[cnt] = fir[x]; fir[x] = cnt; }

int f[MAXN][17], dep[MAXN], dfn[MAXN], tmr, stk[MAXN], tot, top;

void dfs(int u, int ff) {

	int bot = top; dfn[u] = ++tmr;

	dep[u] = dep[f[u][0]=ff] + 1;

	for(int i = fir[u]; i; i = nxt[i])

		if(to[i] != ff) {

			dfs(to[i], u);

			if(top-bot > Block) {

				++tot; while(top > bot) bel[stk[top--]] = tot;

			}

		}

	stk[++top] = u;

}

inline void Pre() {

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

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

			f[i][j] = f[f[i][j-1]][j-1];

}

inline int lca(int u, int v) {

	if(dep[v] > dep[u]) swap(u, v);

	for(int i = 0; i < 17; ++i)

		if((dep[u]-dep[v])&(1<<i)) u = f[u][i];

	if(u == v) return u;

	for(int i = 16; ~i; --i)

		if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];

	return f[u][0];

}

inline void upd(int i) {

	if(!vis[i]) {

		vis[i] = 1;

		Ans += 1ll * V[a[i]] * W[++val[a[i]]];

	}

	else {

		vis[i] = 0;

		Ans -= 1ll * V[a[i]] * W[val[a[i]]--];

	}

}

inline void mdf(int i, int col) {

	if(!vis[i]) { a[i] = col; return; }

	upd(i), a[i] = col, upd(i);

}

inline void rev(int u, int v) {

	while(u != v) {

		if(dep[v] > dep[u]) swap(u, v);

		upd(u), u = f[u][0];

	}

}

int main () {

	read(n), read(m), read(q); Block = pow(n, 0.67);

	for(int i = 1; i <= m; ++i) read(V[i]);

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

	for(int i = 1, x, y; i < n; ++i) read(x), read(y), add(x, y), add(y, x);

	for(int i = 1; i <= n; ++i) read(a[i]), la[i] = a[i];

	dfs(1, 0); Pre();

	if(top) ++tot; while(top) bel[stk[top--]] = tot;

	int cntc = 0, cntq = 0, opt, x, y;

	while(q--) {

		read(opt), read(x), read(y);

		if(!opt) C[++cntc] = (Change){ x, la[x], y }, la[x] = y;

		else {

			if(dfn[x] > dfn[y]) swap(x, y);

			Q[++cntq] = (Query){ x, y, cntc, cntq };

		}

	}

	sort(Q + 1, Q + cntq + 1);

	int TIMES = 0, LCA = lca(Q[1].u, Q[1].v);

	while(TIMES < Q[1].t) ++TIMES, mdf(C[TIMES].i, C[TIMES].v);

	rev(Q[1].u, Q[1].v);

	upd(LCA), ans[Q[1].id] = Ans, upd(LCA);

	for(int i = 2; i <= cntq; ++i) {

		while(TIMES < Q[i].t) ++TIMES, mdf(C[TIMES].i, C[TIMES].v);

		while(TIMES > Q[i].t) mdf(C[TIMES].i, C[TIMES].u), --TIMES;

		rev(Q[i-1].u, Q[i].u), rev(Q[i-1].v, Q[i].v), LCA = lca(Q[i].u, Q[i].v);

		upd(LCA), ans[Q[i].id] = Ans, upd(LCA);

	}

	for(int i = 1; i <= cntq; ++i)

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

}

巴特西

BZOJ 3052/Luogu P4074 [wc2013]糖果公园（树上带修莫队）

题面

分析

CODE

最新文章

热门文章

巴特西

BZOJ 3052/Luogu P4074 [wc2013]糖果公园 （树上带修莫队）

题面

分析

CODE

最新文章

热门文章

BZOJ 3052/Luogu P4074 [wc2013]糖果公园（树上带修莫队）