LOJ2001 SDOI2017 树点涂色 LCT、线段树

注意到每一次\(1\ x\)操作相当于一次LCT中的access操作。由LCT复杂度证明可以知道access的总次数不会超过\(O(nlogn)\)，我们只需要模拟这个access的过程并在其中动态统计每一个点的答案。

我们考虑在虚实边切换的过程中即时更新答案。设当前即将把\(y \rightarrow x\)的虚边转换为实边，设此时\(x\)的实儿子为\(p\)。那么对于\(p\)及其子树，所有点到根的路径经过的颜色数量均\(+1\)；对于\(y\)及其所有点的子树，它们经过的颜色的数量均\(-1\)。那么我们只需要实现子树加减，可以使用线段树。

对于\(3\)操作也就是一个子树\(\max\)操作，同样在线段树上维护；\(2\)操作可以知道\(val_{x,y} = val_{1,x} + val_{1,y} - 2val_{1,LCA(x,y)} + 1\)，所以就是线段树上的单点查询。

#include<bits/stdc++.h>

using namespace std;

int read(){

	int a = 0; char c = getchar(); bool f = 0;

	while(!isdigit(c)){f = c == '-'; c = getchar();}

	while(isdigit(c)){

		a = a * 10 + c - 48; c = getchar();

	}

	return f ? -a : a;

}

const int _ = 1e5 + 7;

vector < int > ch[_];

int N , M , dep[_] , dfn[_] , sz[_] , ind[_] , ts , jump[_][20];

namespace segt{

	int mx[_ << 2] , mrk[_ << 2];

#define mid ((l + r) >> 1)

#define lch (x << 1)

#define rch (x << 1 | 1)

	void init(int x , int l , int r){

		if(l == r) mx[x] = dep[ind[l]];

		else{init(lch , l , mid); init(rch , mid + 1 , r); mx[x] = max(mx[lch] , mx[rch]);}

	}

	void mark(int x , int val){mrk[x] += val; mx[x] += val;}

	void down(int x){mark(lch , mrk[x]); mark(rch , mrk[x]); mrk[x] = 0;}

	void modify(int x , int l , int r , int L , int R , int val){

		if(l >= L && r <= R) return mark(x , val);

		down(x);

		if(mid >= L) modify(lch , l , mid , L , R , val);

		if(mid < R) modify(rch , mid + 1 , r , L , R , val);

		mx[x] = max(mx[lch] , mx[rch]);

	}

	int qry(int x , int l , int r , int L , int R){

		if(l >= L && r <= R) return mx[x];

		int mx = 0; down(x);

		if(mid >= L) mx = qry(lch , l , mid , L , R);

		if(mid < R) mx = max(mx , qry(rch , mid + 1 , r , L , R));

		return mx;

	}

#undef lch

#undef rch

}

namespace LCT{

	int fa[_] , ch[_][2];

	bool son(int x){return ch[fa[x]][1] == x;}

	bool nroot(int x){return ch[fa[x]][1] == x || ch[fa[x]][0] == x;}

	void rot(int x){

		bool f = son(x); int y = fa[x] , z = fa[y] , w = ch[x][f ^ 1];

		fa[x] = z; if(nroot(y)) ch[z][son(y)] = x;

		fa[y] = x; ch[x][f ^ 1] = y;

		ch[y][f] = w; if(w) fa[w] = y;

	}

	void splay(int x){while(nroot(x)){if(nroot(fa[x])) rot(son(fa[x]) == son(x) ? fa[x] : x); rot(x);}}

	void access(int x){

		for(int y = 0 ; x ; y = x , x = fa[x]){

			splay(x);

			if(ch[x][1]){

				int t = ch[x][1]; while(ch[t][0]) t = ch[t][0];

				segt::modify(1 , 1 , N , dfn[t] , dfn[t] + sz[t] - 1 , 1);

			}

			if(y){

				int t = y; while(ch[t][0]) t = ch[t][0];

				segt::modify(1 , 1 , N , dfn[t] , dfn[t] + sz[t] - 1 , -1);

			}

			ch[x][1] = y; fa[y] = x;

		}

	}

}

void dfs(int x , int p){

	dep[x] = dep[p] + 1; ind[dfn[x] = ++ts] = x; sz[x] = 1;

	jump[x][0] = p; LCT::fa[x] = p;

	for(int i = 1 ; jump[x][i - 1] ; ++i) jump[x][i] = jump[jump[x][i - 1]][i - 1];

	for(auto t : ch[x]) if(t != p){dfs(t , x); sz[x] += sz[t];}

}

int LCA(int x , int y){

	if(dep[x] < dep[y]) swap(x , y);

	for(int i = 18 ; i >= 0 ; --i)

		if(dep[x] - (1 << i) >= dep[y]) x = jump[x][i];

	if(x == y) return x;

	for(int i = 18 ; i >= 0 ; --i)

		if(jump[x][i] != jump[y][i]){x = jump[x][i]; y = jump[y][i];}

	return jump[x][0];

}

int main(){

#ifndef ONLINE_JUDGE

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

	freopen("out","w",stdout);

#endif

	N = read(); M = read();

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

		int a = read() , b = read();

		ch[a].push_back(b); ch[b].push_back(a);

	}

	dfs(1 , 0); segt::init(1 , 1 , N); int x , y , z;

	while(M--)

		switch(read()){

		case 1: LCT::access(read()); break;

		case 2:

			x = read(); y = read(); z = LCA(x , y);

			printf("%d\n" , segt::qry(1 , 1 , N , dfn[x] , dfn[x]) + segt::qry(1 , 1 , N , dfn[y] , dfn[y])

				   - 2 * segt::qry(1 , 1 , N , dfn[z] , dfn[z]) + 1); break;

		case 3: x = read(); printf("%d\n" , segt::qry(1 , 1 , N , dfn[x] , dfn[x] + sz[x] - 1));

		}

	return 0;

}

巴特西

LOJ2001 SDOI2017 树点涂色 LCT、线段树

最新文章

热门文章