[树剖]bzoj1036 - cool's Blog

[树剖]bzoj1036

cool posted @ 2015年10月25日 20:28 in 树剖 , 428 阅读

bzoj传送门

十天时间学了树剖(= =)

这是道裸题,只要单点修改,区间查询。

深搜如下

void FHE(int x,int father,int depth)
{
	fa[x] = father;dep[x] = depth;
	size[x] = 1;
	int maxsize = 0;
	son[x] = 0;
	for (int i = head[x];i;i = last[i])
		if (!visit[h[i]])
		{
			visit[h[i]] = 1;
			FHE(h[i],x,depth+1);
			size[x] += size[h[i]];
			if (size[h[i]] > maxsize)
			{
				maxsize = size[h[i]];
				son[x] = h[i];
			}
		}
}
void CHE(int x,int ancestor)
{
	tid[x] = ++label;
	optid[label] = x;
	top[x] = ancestor;
	if (son[x]) {visit[son[x]] = 1;CHE(son[x],ancestor);}
	for (int i = head[x];i;i = last[i])
		if (!visit[h[i]])
		{
			visit[h[i]] = 1;
			CHE(h[i],h[i]);
		}
}

查询如下

int Respond_max(int x,int y)
{
	int ans = -100000000;
	for (;top[x]-top[y];)
	{
		if (dep[top[x]] < dep[top[y]]) swap(x,y);
		ans = max(ans,tree.query_max(1,tid[top[x]],tid[x]));//tree.query_max就是数据结构的最值查询
		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x,y);
	return max(ans,tree.query_max(1,tid[x],tid[y]));
}
int Respond_num(int x,int y)
{
	int ans = 0;
	for (;top[x]-top[y];)
	{
		if (dep[top[x]] < dep[top[y]]) swap(x,y);
		ans += tree.query_num(1,tid[top[x]],tid[x]);//tree.query_num就是数据结构的和查询

		x = fa[top[x]];
	}
	if (dep[x] > dep[y]) swap(x,y);
	return ans+tree.query_num(1,tid[x],tid[y]);
}

 

Avatar_small
Flandre Scarlet 说:
2015年11月15日 18:47

%%%%%%%%%%树剖能手AK大师qlj

Avatar_small
orz hhw 说:
2015年11月15日 20:53

%%%%%%%%%%树剖能手AK大师qlj

HPBOSE 12th Question 说:
2022年8月18日 18:06

HPBOSE 12th New Question Paper 2023 Download, HPBOSE is popular knows as Himachal Pradesh Board Of School Education. HPBOSE 12th Question Paper 2023 It is one of the large board in India. Himachal Pradesh Board is going to conduct Class 12th annual examination for those candidates who have successfully registered for 12th boards exams in 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee