[树剖]bzoj1036 - cool's Blog

[树剖]bzoj1036

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

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


登录 *


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