TJOI2016&HEOI2016 树

wjh15101051's space

卧薪尝胆，厚积薄发。

TJOI2016&HEOI2016 树

Date: Tue Aug 21 11:51:13 CST 2018

In Category: NoCategory

Description：

给一棵以 $1$ 为根的树，刚开始只有 $1$ 号节点有标记，每次对一个节点打标记，或询问它及它的祖先中离他最近的打了标记的节点。

$1\le n \le 100000$

Solution：

倒序处理，把打标记改成删标记，那么删标记的影响就是原来第一个打了标记的祖先是这个点的点祖先变成了它的第一个打了标记的祖先，于是用并查集维护，如果这个点标记撤销就把他和他的父亲合并，询问直接查根就行了。

注意一个点标记可以打多次。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int fa[MAXN];

void dfs(int k)

{

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs(e[i].to);

		}

	}

	return;

}

int f[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

struct opt

{

	int type,val,ans;

}p[MAXN];

int getc()

{

	char c = getchar();

	while(c != 'C' && c != 'Q')c = getchar();

	return (c == 'C' ? 0 : 1);

}

bool tag[MAXN];

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

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

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs(1);

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

	memset(tag,false,sizeof(tag));

	tag[1] = true;

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

	{

		p[i].type = getc();scanf("%d",&p[i].val);

		if(p[i].type == 0)

		{

			if(tag[p[i].val])p[i].val = 0;

			tag[p[i].val] = true;

		}

	}

	for(int i = 1;i <= n;++i)if(!tag[i])f[i] = fa[i];

	for(int i = m;i >= 1;--i)

	{

		if(p[i].type == 0)f[p[i].val] = find(fa[p[i].val]);

		else p[i].ans = find(p[i].val);

	}

	for(int i = 1;i <= m;++i)if(p[i].type)cout << p[i].ans << endl;

	return 0;

}

In tag: 数据结构-并查集

wjh15101051