暴力【p4092】[HEOI2016/TJOI2016]树

Description

在2016年，佳媛姐姐刚刚学习了树，非常开心。现在他想解决这样一个问题：给定一颗有根树（根为1），有以下两种操作：

标记操作：对某个结点打上标记（在最开始，只有结点1有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）

你能帮帮他吗?

Input

输入第一行两个正整数N和Q分别表示节点个数和操作次数

接下来N-1行，每行两个正整数u,v(1≤u,v≤n)表示u到v有一条有向边

接下来Q行，形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询问操作对于每次询问操作。

Output

输出一个正整数，表示结果。

令人窒息的一个题,洛谷上暴力\(A\)了？

但是bzoj上T的飞起 emm

听学长说,这题是树剖。

但是暴力\(A\)掉了。于是写正解就向后拖一拖 emmm

小优化：如果没有修改操作,直接输出\(1\)。

代码

#include<cstdio>

#include<iostream>

#include<algorithm>

#define R register

using namespace std;

const int gz=100008;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,q;

int f[gz],tg[gz];

char opt[5];

inline int work(R int x)

{

	if(tg[x])return x;

	while(f[x])

	{

		x=f[x];

		if(tg[x])return x;

	}

}

bool flg;

int main()

{

	in(n),in(q);

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

		in(x),in(y),f[y]=x;

	tg[1]=true;

	for(R int i=1,x;i<=q;i++)

	{

		scanf("%s",opt+1);

		if(opt[1]=='Q')

		{

			in(x);

			if(!flg)puts("1");

			else printf("%d\n",work(x));

		}

		else

		{

			in(x),flg=true;

			tg[x]=true;

		}

	}

}

巴特西

暴力【p4092】[HEOI2016/TJOI2016]树

Description

Input

Output

最新文章

热门文章

巴特西

暴力 【p4092】[HEOI2016/TJOI2016]树

Description

Input

Output

最新文章

热门文章

暴力【p4092】[HEOI2016/TJOI2016]树