题目链接：BZOJ - 1036

题目分析

这道题可以用树链剖分，块状树等多种方法解决，也可以使用 LCT。

修改某个点的值时，先将它 Splay 到它所在的 Splay 的根，然后修改它的值，再将它 Update 一下。

(1)

询问 x, y 两点之间的路径时，假设 x 是深度小的那一个，先 Access(x) ，然后再 Access(y) 的返回值就是 x, y 的 LCA 。

这时从 x 到 LCA 的路径已经在 LCA 处断开了。我们将 x Splay 一下，然后就是 x 所在的 Splay， LCA， Son[LCA][1] 这 3 部分组成了 x, y 的路径。

要特判 x == LCA 的情况。

(2)

在询问 x, y 两点之间的路径时，也可以用下面的方法:

将 x 变为这棵树的根，然后 Access(y) ，就是求 y 到根的路径了。

为了实现把一个点变为根，需要将这个点到当前树根的路径翻转，就是说，Access(x) , Splay(x), Reverse(x) 。

然后需要注意的就是翻转标记的下传，当要改变 Splay 的形态之前，就需要将涉及到的点 PushDown 一下，使他们没有标记。

比如 Rotate 的时候，或者 Access 中断掉 x 的右子树之前。一定要注意！

Rotate(x) 时， y = Father[x] ，要先 PushDown(y); PushDown(x); 然后再做下面的操作。

代码

不换根的代码：

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

inline void Read(int &Num)

{

	char c = getchar();

	bool Neg = false;

	while (c < '0' || c > '9')

	{

		if (c == '-') Neg = true;

		c = getchar();

	}

	Num = c - '0'; c = getchar();

	while (c >= '0' && c <= '9')

	{

		Num = Num * 10 + c - '0';

		c = getchar();

	}

	if (Neg) Num = -Num;

}

const int MaxN = 30000 + 5, INF = 999999999;

int n, q, Ans;

int A[MaxN], Father[MaxN], Sum[MaxN], Max[MaxN], Son[MaxN][2], Depth[MaxN];

bool isRoot[MaxN];

struct Edge

{

	int v;

	Edge *Next;

} E[MaxN * 2], *P = E, *Point[MaxN];

inline void AddEdge(int x, int y)

{

	++P; P -> v = y;

	P -> Next = Point[x]; Point[x] = P;

}

void DFS(int x, int Fa, int Dep)

{

	Father[x] = Fa; Depth[x] = Dep;

	for (Edge *j = Point[x]; j; j = j -> Next)

	{

		if (j -> v == Fa) continue;

		DFS(j -> v, x, Dep + 1);

	}

}

inline int gmin(int a, int b) {return a < b ? a : b;}

inline int gmax(int a, int b) {return a > b ? a : b;}

inline void Update(int x)

{

	Max[x] = gmax(A[x], gmax(Max[Son[x][0]], Max[Son[x][1]]));

	Sum[x] = A[x] + Sum[Son[x][0]] + Sum[Son[x][1]];

}

void Rotate(int x, int f)

{

	int y = Father[x];

	if (isRoot[y])

	{

		isRoot[y] = false;

		isRoot[x] = true;

	}

	else

	{

		if (y == Son[Father[y]][0]) Son[Father[y]][0] = x;

		else Son[Father[y]][1] = x;

	}

	Father[x] = Father[y];

	Son[y][f ^ 1] = Son[x][f];

	if (Son[x][f]) Father[Son[x][f]] = y;

	Son[x][f] = y;

	Father[y] = x;

	Update(y);

	Update(x);

}

void Splay(int x)

{

	int y;

	while (!isRoot[x])

	{

		y = Father[x];

		if (isRoot[y])

		{

			if (x == Son[y][0]) Rotate(x, 1);

			else Rotate(x, 0);

			break;

		}

		if (y == Son[Father[y]][0])

		{

			if (x == Son[y][0])

			{

				Rotate(y, 1);

				Rotate(x, 1);

			}

			else

			{

				Rotate(x, 0);

				Rotate(x, 1);

			}

		}

		else

		{

			if (x == Son[y][1])

			{

				Rotate(y, 0);

				Rotate(x, 0);

			}

			else

			{

				Rotate(x, 1);

				Rotate(x, 0);

			}

		}

	}

}

int Access(int x)

{

	int y = 0;

	while (x != 0)

	{

		Splay(x);

		isRoot[Son[x][1]] = true;

		Son[x][1] = y;

		if (y) isRoot[y] = false;

		Update(x);

		y = x;

		x = Father[x];

	}

	return y;

}

char Str[10];

int main()

{

	scanf("%d", &n);

	int a, b, LCA;

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

	{

		Read(a); Read(b);

		AddEdge(a, b); AddEdge(b, a);

	}

	DFS(1, 0, 0);

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

	{

		Read(A[i]);

		isRoot[i] = true;

		Sum[i] = Max[i]= A[i];

	}

	Sum[0] = 0; Max[0] = -INF;

	scanf("%d", &q);

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

	{

		scanf("%s", Str);

		Read(a); Read(b);

		if (strcmp(Str, "CHANGE") == 0)

		{

			Splay(a);

			A[a] = b;

			Update(a);

		}

		else if (strcmp(Str, "QMAX") == 0)

		{

			if (Depth[a] > Depth[b]) swap(a, b);

			Access(a);

			LCA = Access(b);

			Splay(a);

			if (a == LCA) Ans = gmax(A[LCA], Max[Son[LCA][1]]);

			else Ans = gmax(A[LCA], gmax(Max[a], Max[Son[LCA][1]]));

			printf("%d\n", Ans);

		}

		else if (strcmp(Str, "QSUM") == 0)

		{

			if (Depth[a] > Depth[b]) swap(a, b);

			Access(a);

			LCA = Access(b);

			Splay(a);

			if (a == LCA) Ans = A[LCA] + Sum[Son[LCA][1]];

			else Ans = A[LCA] + Sum[a] + Sum[Son[LCA][1]];

			printf("%d\n", Ans);

		}

	}

	return 0;

}

换根的代码：

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

inline void Read(int &Num)

{

	char c = getchar();

	bool Neg = false;

	while (c < '0' || c > '9')

	{

		if (c == '-') Neg = true;

		c = getchar();

	}

	Num = c - '0'; c = getchar();

	while (c >= '0' && c <= '9')

	{

		Num = Num * 10 + c - '0';

		c = getchar();

	}

	if (Neg) Num = -Num;

}

inline int gmin(int a, int b) {return a < b ? a : b;}

inline int gmax(int a, int b) {return a > b ? a : b;}

const int MaxN = 30000 + 5, INF = 999999999;

int n, q;

int A[MaxN], Father[MaxN], Son[MaxN][2], Max[MaxN], Sum[MaxN];

bool isRoot[MaxN], Rev[MaxN];

struct Edge

{

	int v;

	Edge *Next;

} E[MaxN * 2], *P = E, *Point[MaxN];

inline void AddEdge(int x, int y)

{

	++P; P -> v = y;

	P -> Next = Point[x]; Point[x] = P;

}

void DFS(int x, int Fa)

{

	Father[x] = Fa;

	for (Edge *j = Point[x]; j; j = j -> Next)

	{

		if (j -> v == Fa) continue;

		DFS(j -> v, x);

	}

}

inline void Reverse(int x)

{

	Rev[x] = !Rev[x];

	swap(Son[x][0], Son[x][1]);

}

inline void PushDown(int x)

{

	if (!Rev[x]) return;

	Rev[x] = false;

	if (Son[x][0]) Reverse(Son[x][0]);

	if (Son[x][1]) Reverse(Son[x][1]);

}

inline void Update(int x)

{

	Sum[x] = Sum[Son[x][0]] + Sum[Son[x][1]] + A[x];

	Max[x] = gmax(A[x], gmax(Max[Son[x][0]], Max[Son[x][1]]));

}

void Rotate(int x)

{

	int y = Father[x], f;

	PushDown(y);

	PushDown(x);

	if (x == Son[y][0]) f = 1;

	else f = 0;

	if (isRoot[y])

	{

		isRoot[y] = false;

		isRoot[x] = true;

	}

	else

	{

		if (y == Son[Father[y]][0]) Son[Father[y]][0] = x;

		else Son[Father[y]][1] = x;

	}

	Father[x] = Father[y];

	Son[y][1 ^ f] = Son[x][f];

	if (Son[x][f]) Father[Son[x][f]] = y;

	Son[x][f] = y;

	Father[y] = x;

	Update(y);

	Update(x);

}

void Splay(int x)

{

	int y;

	while (!isRoot[x])

	{

		y = Father[x];

		if (isRoot[y])

		{

			Rotate(x);

			break;

		}

		if (y == Son[Father[y]][0])

		{

			if (x == Son[y][0])

			{

				Rotate(y);

				Rotate(x);

			}

			else

			{

				Rotate(x);

				Rotate(x);

			}

		}

		else

		{

			if (x == Son[y][1])

			{

				Rotate(y);

				Rotate(x);

			}

			else

			{

				Rotate(x);

				Rotate(x);

			}

		}

	}

}

int Access(int x)

{

	int y = 0;

	while (x != 0)

	{

		Splay(x);

		PushDown(x);

		isRoot[Son[x][1]] = true;

		Son[x][1] = y;

		if (y) isRoot[y] = false;

		Update(x);

		y = x;

		x = Father[x];

	}

	return y;

}

void Make_Root(int x)

{

	int t = Access(x);

	Reverse(t);

}

int main()

{

	scanf("%d", &n);

	int a, b, c;

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

	{

		Read(a); Read(b);

		AddEdge(a, b); AddEdge(b, a);

	}

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

	DFS(1, 0);

	Max[0] = -INF; Sum[0] = 0;

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

	{

		isRoot[i] = true;

		Sum[i] = Max[i] = A[i];

	}

	scanf("%d", &q);

	char Str[10];

	int Ans, LCA;

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

	{

		scanf("%s", Str);

		Read(a); Read(b);

		if (strcmp(Str, "CHANGE") == 0)

		{

			Splay(a);

			A[a] = b;

			Update(a);

 		}

		else

		{

			Make_Root(a);

			c = Access(b);

			if (strcmp(Str, "QMAX") == 0) printf("%d\n", Max[c]);

			else printf("%d\n", Sum[c]);

		}

	}

	return 0;

}

　　

最新文章

  1. Java网络编程--简单聊天程序
  2. CentOS 6.5 安装HDFS集群(Hadoop-2.7.3)
  3. HashMap遍历方式探究
  4. html5 语义
  5. 转: CSS中overflow的用法
  6. QQ登入（6）腾讯微博-获取微博用户信息，发送微博
  7. ResultSet的getInt(),getString()方法
  8. 在js中获取easyui datagrid的数据
  9. Linux&amp;shell 之Shell命令进阶
  10. DOS的BAT技巧两则
  11. Android 打开系统相册和系统视
  12. C# DataRow[]转换DataTable
  13. win8 explorer 进程频繁奔溃的原因及处理
  14. python链接mysql以及常用语法
  15. [转]SQL Server 表变量和临时表的区别
  16. 记录python接口自动化测试--pycharm执行测试用例时需要使用的姿势（解决if __name__ == &quot;__main__&quot;:里面的程序不生效的问题）(第三目)
  17. SharePoint 2007 单列表模糊查询SPD定制
  18. Mybatis 系列9
  19. 我眼中的Adaboost
  20. nginx 配置文件学习

热门文章

  1. linux IO 内核参数调优 之 原理和参数介绍
  2. SQL语句中&quot;where 1=1&quot;和&quot;where 1=0&quot;的作用
  3. Java基础知识强化之网络编程笔记08：TCP之客户端键盘录入服务器控制台输出
  4. Python获取web页面信息
  5. 会话技术之Cookie 和 Session
  6. Java 之文件IO编程 之读取
  7. 使用Druid作为数据源
  8. Asp.Net MVC Ajax
  9. matlab中max的用法
  10. php编译安装扩展curl