【BZOJ 4551】[TJOI2016&HEOI2016] 树

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4551
双倍经验:http://www.lydsy.com/JudgeOnline/problem.php?id=3319
神犇题解:http://medalplus.com/?p=1685

题解

  1. 强制在线做法 O(nlogn)
    考虑每一次标记点:只会影响其子树中的点
    所以使用DFS序+线段树就可以辣!

  2. 离线做法 O(nlogn)
    考虑将每一次标记的时间记录到点上
    然后使用倍增LCA的思想向上倍增

  3. 离线做法 O(nα(n))
    考虑离线之后进行逆序操作
    这样的话,操作就变成了删除标记
    这个可以形象地想成:打通了向上走地道路
    于是使用并查集即可
    ps:和BZOJ_3319是一毛一样的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;

int head[N],to[N],nxt[N],anc[N],fa[N];
int n,m,tot,opt[N],tag[N],vout[N];
char pat[10];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int find(int w) {
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w], fa[w]=f, w=tmp;
	return f;
}

inline void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

void DFS(int w, int last) {
	if (tag[w]) last = fa[w] = w;
	else fa[w] = last;
	for (int i=head[w];i;i=nxt[i]) {
		anc[to[i]] = w;
		DFS(to[i],last);
	}
}

int main(){
	n = read(); m = read();
	for (int i=1,u,v;i<n;i++) {
		u = read(); v = read();
		Add_Edge(u,v);
	}
	for (int i=1;i<=m;i++) {
		scanf("%s",pat+1);
		opt[i] = read(); 
		if (pat[1] == 'C') tag[opt[i]]++;
		else opt[i] *= -1;
	}
	tag[1]++; DFS(1,1);
	for (int i=m;i;i--) {
		if (opt[i] > 0) {
			if (!(--tag[opt[i]])) {
				fa[opt[i]] = anc[opt[i]];
			}
		} else {
			vout[++tot] = find(-opt[i]);
		}
	}
	while (tot) printf("%d\n",vout[tot--]); 
	return 0;
}

2 thoughts to “【BZOJ 4551】[TJOI2016&HEOI2016] 树”

  1. you are really a good webmaster. The website loading speed is amazing. It seems that you’re doing any unique trick. In addition, The contents are masterwork. you’ve done a fantastic job on this topic!

Leave a Reply

Your email address will not be published. Required fields are marked *