【CodeForces】1172E. Nauuo and ODT

题解

看了一遍题解（以及代码）但是没写代码……

后来做梦的时候忽然梦到了这道题……意识到我需要补一下……

这道题就是，对于每种颜色，把没有染成这种颜色的点标成黑点，然后计算每个联通块的平方

然后每个点维护，虚儿子黑点的siz，虚儿子的siz的平方，还有splay上的siz和

为了保证最高点是白点，我们新建一个点建到根上面

然后把一个点染黑就相当于断掉所有儿子，然后减去所有虚儿子siz的平方，然后顺着fa找到最高的白点，删掉这个白点原先右边挂着的树，然后再减去这个白点原先右边挂着的部分，这个点再连上父亲，再找到最高的白点，重新统计白点右边挂着的部分

把一个点染白相当于找到最高的白点，然后右边挂着的树给删掉，然后加上x所在的虚儿子siz的平方，再最高的白点新的右子树大小

代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <vector>

#include <random>

#include <ctime>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define MAXN 400005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef double db;

template<class T>

void read(T &res) {

	res = 0;T f = 1;char c = getchar();

	while(c < '0' || c > '9') {

		if(c == '-') f = -1;

		c = getchar();

	}

	while(c >= '0' && c <= '9') {

		res = res * 10 + c - '0';

		c = getchar();

	}

	res *= f;

}

template<class T>

void out(T x) {

	if(x < 0) {x = -x;putchar('-');}

	if(x >= 10) out(x / 10);

	putchar('0' + x % 10);

}

int N,M;

int c[MAXN],b[MAXN];

int64 ans,del[MAXN];

struct node {

	int lc,rc,fa;

	int64 siz2i,siz,sizi;

}tr[MAXN];

#define rc(u) tr[u].rc

#define lc(u) tr[u].lc

#define fa(u) tr[u].fa

#define siz(u) tr[u].siz

#define siz2i(u) tr[u].siz2i

#define sizi(u) tr[u].sizi

int fa[MAXN];

vector<int> E[MAXN];

vector<pii > col[MAXN];

void dfs(int u) {

	for(auto v : E[u]) {

		if(v != fa[u]) {

			fa[v] = u;

			dfs(v);

		}

	}

}

int64 o(int64 x) {

	return x * x;

}

bool isRoot(int x) {

	if(!fa(x)) return true;

	else return lc(fa(x)) != x && rc(fa(x)) != x;

}

bool which(int x) {

	return rc(fa(x)) == x;

}

void update(int u) {

	siz(u) = sizi(u) + siz(rc(u)) + siz(lc(u)) + 1;

}

void rotate(int u) {

	int v = fa(u),w = fa(v);

	if(!isRoot(v)) {(v == lc(w) ? lc(w) : rc(w)) = u;}

	fa(u) = w;fa(v) = u;

	int b = u == lc(v) ? rc(u) : lc(u);

	if(b) fa(b) = v;

	if(u == lc(v)) {rc(u) = v;lc(v) = b;}

	else {lc(u) = v;rc(v) = b;}

	update(v);

}

void Splay(int u) {

	while(!isRoot(u)) {

		if(!isRoot(fa(u))) {

			if(which(u) == which(fa(u))) rotate(fa(u));

			else rotate(u);

		}

		rotate(u);

	}

	update(u);

}

void Access(int u) {

	for(int x = 0 ; u ; x = u, u = fa(u)) {

		Splay(u);

		sizi(u) += siz(rc(u));

		sizi(u) -= siz(x);

		siz2i(u) += o(siz(rc(u)));

		siz2i(u) -= o(siz(x));

		rc(u) = x;

		update(u);

	}

}

int FindRoot(int x) {

	Access(x);Splay(x);

	int p = x;

	while(lc(p)) p = lc(p);

	return p;

}

void Link(int x) {

	int y = fa[x],z = FindRoot(y);

	Access(y);Splay(z);

	ans -= o(siz(rc(z)));

	Access(x);

	ans -= siz2i(x);

	tr[x].fa = y;

	Splay(y);

	siz2i(y) += o(siz(x));

	sizi(y) += siz(x);

	update(y);

	Access(x);Splay(z);//这里要Access(x)因为可能y是一个白点

	ans += o(siz(rc(z)));

}

void Cut(int x) {

	int y = fa[x],z = FindRoot(y);

	Access(x);Splay(z);

	ans -= o(siz(rc(z)));

	ans += siz2i(x);

	Splay(y);

	rc(y) = 0;fa(x) = 0;update(y);

	Splay(z);

	ans += o(siz(rc(z)));

}

void Init() {

	read(N);read(M);

	for(int i = 1 ; i <= N ; ++i) read(c[i]);

	int a,b;

	for(int i = 1 ; i < N ; ++i) {

		read(a);read(b);

		E[a].pb(b);E[b].pb(a);

	}

	dfs(1);fa[1] = N + 1;

	for(int i = 1 ; i <= N ; ++i) {

		col[c[i]].pb(mp(0,i));

	}

	for(int i = 1 ; i <= M ; ++i) {

		read(a);read(b);

		col[b].pb(mp(i,a));

		col[c[a]].pb(mp(i,a));

		c[a] = b;

	}

}

void Solve() {

	for(int i = 1 ; i <= N ; ++i) {siz(i) = 1;Link(i);}

	for(int i = 1 ; i <= N ; ++i) {

		del[0] += 1LL * N * N;

		int64 pre = 1LL * N * N;

		for(int j = 0 ; j < col[i].size() ; ++j) {

			int t = j;

			del[col[i][j].fi] -= pre;

			while(t + 1 < col[i].size() && col[i][t + 1].fi == col[i][j].fi) ++t;

			for(int h = j ; h <= t ; ++h) {

				if(!b[col[i][h].se]) {Cut(col[i][h].se);}

				else {Link(col[i][h].se);}

				b[col[i][h].se] ^= 1;

			}

			pre = ans;

			del[col[i][j].fi] += ans;

			j = t;

		}

		for(int j = 0 ; j < col[i].size() ; ++j) {

			if(b[col[i][j].se]) {

				b[col[i][j].se] = 0;

				Link(col[i][j].se);

			}

		}

	}

	for(int i = 0 ; i <= M ; ++i) {

		if(i) del[i] += del[i - 1];

		out(1LL * N * N * N - del[i]);enter;

	}

}

int main() {

#ifdef ivorysi

	freopen("f1.in","r",stdin);

#endif

	Init();

	Solve();

	return 0;

}

巴特西

【CodeForces】1172E. Nauuo and ODT

题解

代码

最新文章

热门文章