Lowest Common Ancestor 最近公共祖先

2 ways to brute forces, find LCA(x, y) 2种暴力方式

  1. 先标记x的所有祖先节点，y向上跳，直到遇到一个被标记的节点。
  2. 先把x和y调整成深度一样的，然后当x和y不同，同时向上跳。

一些有意义的算法

  1. 倍增，O(nlog⁡n)O(n \log n)预处理，单个询问 O(log⁡n)O(\log n) \
  2. Tarjan求LCA，是一个离线时间复杂度 O(n+q)O(n + q) \
  3. DFS序+RMQ，时间复杂度 O(nlogn)O(n log n) 预处理，单个询问 O(1)O(1)
  4. 树链剖分，O(n)预处理，单个询问 O(log⁡n)O(\log n)
  5. 理论最优，O(n)预处理，单个询问 O(1)O(1)

parent[x]

f[x][i]

f[x][0] = parent[x]
f[x][1] = parent[parent[x]]
f[x][2] = parent[parent[parent[parent[x]]]]
f[x][y] = f[f[x][y-1]][y-1]

from x go up 2**i steps, 

parent[parent[parent[... parent[x]]]]
2**i parents.


from x go up 17 steps

f[f[x][0]][4]

https://oi-wiki.org/graph/hld/

为什么 树链剖分 好
树链剖分的最坏情况，二叉树
一般不会有人主动去构造二叉树

随机一个树，深度不会太深，所以暴力LCA其实很快
为了卡暴力，会生成一些比较长的链
树链剖分 可以 BFS 空间 O(n)

倍增算法和树链剖分最有用
他们都是在线，并且足够块

倍增算法是最容易理解和实现的算法
树链剖分很快
树链剖分的最坏情况是二叉树，不是长链
出题人一般不会出二叉树

P3379 【模板】最近公共祖先（LCA）

https://www.luogu.com.cn/problem/P3379

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N−1N-1 行每行包含两个正整数 x,yx, y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 MM 行每行包含两个正整数 a,ba, b，表示询问 aa 结点和 bb 结点的最近公共祖先。

输出格式

输出包含 MM 行，每行包含一个正整数，依次为每一个询问的结果。

样例 #1

样例输入 #1
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
样例输出 #1
4
4
1
4
4

提示

对于 30%30\% 的数据，N≤10N\leq 10，M≤10M\leq 10。

对于 70%70\% 的数据，N≤10000N\leq 10000，M≤10000M\leq 10000。

对于 100%100\% 的数据，N≤500000N\leq 500000，M≤500000M\leq 500000。

样例说明：

该树结构如下：

第一次询问：2,42, 4 的最近公共祖先，故为 44。

第二次询问：3,23, 2 的最近公共祖先，故为 44。

第三次询问：3,53, 5 的最近公共祖先，故为 11。

第四次询问：1,21, 2 的最近公共祖先，故为 44。

第五次询问：4,54, 5 的最近公共祖先，故为 44。

故输出依次为 4,4,1,4,44, 4, 1, 4, 4。

2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, s;
vector<int> a[500020];
int f[500020][20];
int d[500020];
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int i: a[x]) {
		if (i != y) {
			dfs(i, x);
		}
	}
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(s, 0);
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d\n", lca(x, y));
	}
	return 0;
}

题解

binary lifting

DFS and RMQ

https://github.com/wwwwodddd/Zukunft/blob/master/luogu/P3379__.cpp

P5836 [USACO19DEC]Milk Visits S

https://www.luogu.com.cn/problem/P5836

题目描述

Farmer John 计划建造 NN 个农场，用 N−1N-1 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为更赛牛或荷斯坦牛之一。

Farmer John 的 MM 个朋友经常前来拜访他。在朋友 ii 拜访之时，Farmer John 会与他的朋友沿着从农场 AiA_i 到农场 BiB_i 之间的唯一路径行走（可能有 Ai=BiA_i = B_i）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的有些朋友只喝更赛牛的牛奶，其余的只喝荷斯坦牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

输入格式

输入的第一行包含两个整数 NN 和 MM。

第二行包含一个长为 NN 的字符串。如果第 ii 个农场中的奶牛是更赛牛，则字符串中第 ii 个字符为 G，如果第 ii 个农场中的奶牛是荷斯坦牛则为 H。

以下 N−1N-1 行，每行包含两个不同的整数 XX 和 YY（1≤X,Y≤N1 \leq X, Y \leq N），表示农场 XX 与 YY 之间有一条道路。

以下 MM 行，每行包含整数 AiA_i，BiB_i，以及一个字符 CiC_i。AiA_i 和 BiB_i 表示朋友 ii 拜访时行走的路径的端点，CiC_i 是 G 或 H 之一，表示第 ii 个朋友喜欢更赛牛的牛奶或是荷斯坦牛的牛奶。

输出格式

输出一个长为 MM 的二进制字符串。如果第 ii 个朋友会感到高兴，则字符串的第 ii 个字符为 1，否则为 0。

样例 #1

样例输入 #1
5 5
HHGHG
1 2
2 3
2 4
1 5
1 4 H
1 4 G
1 3 G
1 3 H
5 5 H
样例输出 #1
10110

提示

在这里，从农场 1 到农场 4 的路径包括农场 1、2 和 4。所有这些农场里都是荷斯坦牛，所以第一个朋友会感到满意，而第二个朋友不会。

关于部分分：

测试点 11 样例。

测试点 2∼52\sim 5 满足 N≤103N\le 10^3，M≤2⋅103M\le 2\cdot 10^3。

对于 100%100\% 的数据，1≤N≤1051 \leq N \leq 10^5，1≤M≤1051 \leq M \leq 10^5。

供题：Spencer Compton

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
char s[100020];
vector<int> a[100020];
int f[100020][20];
int c[100020];
int d[100020];
void dfs(int x, int y)
{
	f[x][0] = y;
	d[x] = d[y] + 1;
	c[x] = c[y] + (s[x] == 'G');
	for (int i = 1; i < 20; i++)
	{
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int i : a[x])
	{
		if (i != y)
		{
			dfs(i, x);
		}
	}
}
int lca(int x, int y)
{
	if (d[x] < d[y])
	{
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++)
	{
		if (dd >> i & 1)
		{
			x = f[x][i];
		}
	}
	if (x == y)
	{
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--)
	{
		if (f[x][i] != f[y][i])
		{
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main()
{
	scanf("%d%d", &n, &m);
	scanf("%s", s + 1);
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 0; i < m; i++)
	{
		int x, y;
		char o[2];
		scanf("%d%d%s", &x, &y, o);
		int l = lca(x, y);
		int dxy = d[x] + d[y] - 2 * d[l] + 1;
		int cxy = c[x] + c[y] - 2 * c[l] + (s[l] == 'G');
		if (o[0] == 'G')
		{
			printf("%d", cxy > 0);
		}
		else
		{
			printf("%d", cxy < dxy);
		}
	}
	printf("\n");
	return 0;
}

题解

P6098 [USACO19FEB]Cow Land G

https://www.luogu.com.cn/problem/P6098

题目背景

Cow Land 是一个特殊的奶牛游乐园，奶牛们可以在那里漫步，吃美味的草，并参观不同的景点（尤其过山车特别受欢迎）。

题目描述

Cow Land 总共有 NN 个不同的景点（ 2≤N≤1052 \leq N \leq 10^5 ）。 一共有 n−1n-1 条道路连接任意两个景点，这意味着任意两个景点间只有一条简单路径。

每个景点 ii 都有一个享受值 eie_i ，这个值可能会改变。因为一些景点在早上更有吸引力，而其他景点在下午则更能吸引游客。

从景点 ii 到景点 jj 的奶牛们可以欣赏从景点 ii 到景点 jj 的路上的所有景观。这条路线的享受值为景点 ii 到景点 jj 的路上的所有景点（包括景点 ii 和景点 jj ）的享受值按位进行异或运算的结果。

请帮助奶牛确定他们前往 Cow Land 旅行时计划的路线的享受值。

输入格式

输入的第一行包含两个整数， N,QN,Q（1≤Q≤1051 \leq Q \leq 10^5）。

接下来一行包含 NN 个整数，其中第 ii 个整数 eie_i 代表景点 ii 的享受值。

接下来 N−1N-1 行，每行包含两个整数 a,ba,b ，表示景点 aa 和景点 bb 之间有一条道路相连。

最后 QQ 行，每行包含 3 个整数，表示一个操作，具体内容如下：

  1. 1 i v，表示将 eie_i 修改为 vv 。
  2. 2 i j，表示询问从景点 ii 到景点 jj 的路线的享受值为多少。

输出格式

对于每个 2 操作，输出对应查询的结果。

样例 #1

样例输入 #1
5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3
样例输出 #1
21
20
4
20

提示

子任务：对于 50%50\% 的数据，没有修改操作。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<int> a[100020];
int f[100020][20];
int d[100020];
int c[200020];
int w[100020];
int L[100020];
int R[100020];
int ss = 1;
void change(int x, int y) {
	for (int i = x; i <= 2 * n; i += i & -i) {
		c[i] ^= y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re ^= c[i];
	}
	return re;
}
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	L[x] = ss;
	ss++;
	for (int i: a[x]) {
		if (i != y) {
			dfs(i, x);
		}
	}
	R[x] = ss;
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) {
		change(L[i], w[i]);
		change(R[i], w[i]);
	}
	for (int i = 0; i < q; i++) {
		int o, x, y;
		cin >> o >> x >> y;
		if (o == 1) {
			change(L[x], w[x] ^ y);
			change(R[x], w[x] ^ y);
			w[x] = y;
		} else {
			cout << (query(L[x]) ^ query(L[y]) ^ w[lca(x, y)]) << endl;
		}
	}
	return 0;
}

题解

用来和树状数组配合的是进出栈序
有两种使用方法

修改单点，询问子树和
把点权放在第一次出现的位置上
子树和就是区间和

修改单点，询问根节点到某节点的路径和
在第一次出现的位置上加上点权
在第二次出现的位置上减去点权
1 2 2 3 4 4 5 5 3 1

实际实现的时候，可以第二次出现位置不+1
0 1 2 3 4 5 6
1 1
2 2
3 3
4 4
5 5

0 1 2 3 4 5 6 7 8 9 10
1 1
2 2
3 3
4 4
5 5

P4374 [USACO18OPEN]Disruption P

https://www.luogu.com.cn/problem/P4374

题目描述

Farmer John自豪于他所经营的交通发达的的农场。这个农场是由NN块牧场（2≤N≤50,0002 \leq N \leq 50,000）组成的，N−1N-1条双向道路将它们连接起来，每一条道路的都为一单位长度。Farmer John注意到，从任何一块牧场到另一块牧场，都能通过一组合适的道路到达。

尽管FJ的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这事实上会将他的农场分为两个不相交的牧场集合，奶牛们只能够在每一个集合内移动但不能在集合间移动。于是FJ又建造了MM条额外的双向道路（1≤M≤50,0001 \leq M \leq 50,000），每一条的长度都是一个至多为10910^9的正整数。奶牛们仍然可以使用原有的道路进行移动，除非其中的某些被阻断了。

如果某条原有的道路被阻断了，农场就会被分为两块不相交的区域，那么FJ就会从他的额外修建的道路中选择一条能够重建这两块区域的连通性的，取代原来那条，从而奶牛们又可以从任何一块牧场去往另一块牧场。

对于农场上每一条原有的道路，帮助FJ选出最短的替代用的道路。

输入格式

输入的第一行包含NN和MM。接下来的N−1N-1行，每行用整数pp和qq描述了一条原有的道路，其中p≠qp \neq q是这条道路连接的两块牧场（在1…N1 \ldots N范围内）。剩下的MM行，每行用三个整数pp、qq和rr描述了一条额外的道路，其中rr是这条道路的长度。任何两块牧场之间至多只有一条道路。

输出格式

对原有的N−1N-1条道路的每一条，按照它们在输入中出现的顺序，输出如果这条道路被阻断的话，能够重新连接农场的最短的替代用道路的长度。如果不存在合适的替代用的道路，输出-1。

样例 #1

样例输入 #1
6 3
1 2
1 3
4 1
4 5
6 5
2 3 7
3 6 8
6 4 5
样例输出 #1
7
7
8
5
5

提示

供题：Brian Dean

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int> > a[500020];
vector<int> b[500020];
int f[500020][20];
int d[500020];
int z[500020];
multiset<int> s[500020];
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (pair<int, int> i: a[x]) {
		if (i.first != y) {
			dfs(i.first, x);
		}
	}
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
void merge(int x, int y) {
	if (s[x].size() < s[y].size()) {
		s[x].swap(s[y]);
	}
	for (int i: s[y]) {
		s[x].insert(i);
	}
	s[y].clear();
}
void dfs2(int x, int y) {
	for (pair<int, int> i: a[x]) {
		if (i.first != y) {
			dfs2(i.first, x);
			z[i.second] = s[i.first].size() > 0 ? *s[i.first].begin() : -1;
			merge(x, i.first);
		}
	}
	for (int i: b[x]) {
		if (i > 0) {
			s[x].insert(i);
		} else {
			s[x].erase(s[x].find(-i));
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(make_pair(y, i));
		a[y].push_back(make_pair(x, i));
	}
	dfs(1, 0);
	for (int i = 0; i < m; i++) {
		int x, y, z, l;
		scanf("%d%d%d", &x, &y, &z);
		l = lca(x, y);
		b[x].push_back(z);
		b[y].push_back(z);
		b[l].push_back(-z);
		b[l].push_back(-z);
	}
	dfs2(1, 0);
	for (int i = 1; i < n; i++) {
		printf("%d\n", z[i]);
	}
	return 0;
}

题解

DFS and merge by size

Diameter

2 DFS

find the farthest vertex of root, v1

find the farthest vertex of v1, v2

v1, v2 is the diameter.

There might be a solution about coloring.

http://usaco.org/index.php?page=viewproblem2&cpid=866

Every time, we remove a vertex with degree(in the tree) <= 1, and in degree 0.

The last one we removed is a possible solution.

P3128 [USACO15DEC]Max Flow P

https://www.luogu.com.cn/problem/P3128

题目描述

Farmer John has installed a new system of N−1N-1 pipes to transport milk between the NN stalls in his barn (2≤N≤50,0002 \leq N \leq 50,000), conveniently numbered 1…N1 \ldots N. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between KK pairs of stalls (1≤K≤100,0001 \leq K \leq 100,000). For the iith such pair, you are told two stalls sis_i and tit_i, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the KK paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from sis_i to tit_i, then it counts as being pumped through the endpoint stalls sis_i and

tit_i, as well as through every stall along the path between them.

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

输入格式

The first line of the input contains NN and KK.

The next N−1N-1 lines each contain two integers xx and yy (x≠yx \ne y) describing a pipe

between stalls xx and yy.

The next KK lines each contain two integers ss and tt describing the endpoint

stalls of a path through which milk is being pumped.

输出格式

An integer specifying the maximum amount of milk pumped through any stall in the

barn.

样例 #1

样例输入 #1
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
样例输出 #1
9

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[50020];
int f[50020][16];
int d[50020];
int s[50020];
int ans;
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 16; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int i: a[x]) {
		if (i != y) {
			dfs(i, x);
		}
	}
}
int dfs2(int x, int y) {
	int re = s[x];
	for (int i: a[x]) {
		if (i != y) {
			re += dfs2(i, x);
		}
	}
	ans = max(ans, re);
	return re;
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 16; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 16 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		int l = lca(x, y);
		s[x]++;
		s[y]++;
		s[l]--;
		s[f[l][0]]--;
	}
	dfs2(1, 0);
	printf("%d\n", ans);
	return 0;
}

题解

Difference and prefix sum
树上差分

P4281 [AHOI2008]紧急集合 / 聚会

https://www.luogu.com.cn/problem/P4281

题目描述

欢乐岛上有个非常好玩的游戏，叫做“紧急集合”。在岛上分散有 nn 个等待点，有 n−1n-1 条道路连接着它们，每一条道路都连接某两个等待点，且通过这些道路可以走遍所有的等待点，通过道路从一个点到另一个点要花费一个游戏币。

参加游戏的人三人一组，开始的时候，所有人员均任意分散在各个等待点上（每个点同时允许多个人等待），每个人均带有足够多的游戏币（用于支付使用道路的花费）、地图（标明等待点之间道路连接的情况）以及对话机（用于和同组的成员联系）。当集合号吹响后，每组成员之间迅速联系，了解到自己组所有成员所在的等待点后，迅速在 nn 个等待点中确定一个集结点，组内所有成员将在该集合点集合，集合所用花费最少的组将是游戏的赢家。

小可可和他的朋友邀请你一起参加这个游戏，由你来选择集合点，聪明的你能够完成这个任务，帮助小可可赢得游戏吗？

输入格式

第一行两个正整数 nn 和 mm，分别表示等待点的个数（等待点也从 11 到 nn 进行编号）和获奖所需要完成集合的次数。

随后 n−1n-1 行，每行两个正整数 a,ba,b，表示编号为 aa 和编号为 bb 的等待点之间有一条路。

随后 mm 行，每行用三个正整数 x,y,zx,y,z，表示某次集合前小可可、小可可的朋友以及你所在等待点的编号。

输出格式

输出共 mm 行，每行两个用空格隔开的整数 p,cp,c。其中第 ii 行表示第 ii 次集合点选择在编号为 pp 的等待点，集合总共的花费是 cc 个游戏币。

样例 #1

样例输入 #1
6 4  
1 2  
2 3  
2 4 
4 5
5 6
4 5 6
6 3 1
2 4 4 
6 6 6
样例输出 #1
5 2
2 5
4 1
6 0

提示

对于 40%40\% 的数据，n≤2×103n\leq2\times10^3，m≤2×103m\leq2\times 10^3。

对于 100%100\% 的数据，1≤x,y,z≤n≤5×1051\leq x,y,z\leq n\leq 5\times10^5，1≤m≤5×1051\leq m\leq 5\times 10^5。

参考代码

#include <bits/stdc++.h>
using namespace std;
void read(int&x) 
{
	char ch;
	while((ch=getchar())&&(ch<'0'||ch>'9'));
		x=ch-'0';
	while((ch=getchar())&&ch>='0'&&ch<='9')
		x=x*10+ch-'0';
}
int n, m;
int f[500020][20];
int d[500020];
struct Edge {
	int next;
	int to;
} e[1000020];
int h[500020], tot;
void add(int x, int y) {
	tot++;
	e[tot].next = h[x];
	e[tot].to = y;
	h[x] = tot;
}
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int ii = h[x]; ii > 0; ii = e[ii].next) {
		int i = e[ii].to;
		if (i != y) {
			dfs(i, x);
		}
	}
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	read(n);
	read(m);
	// scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		int x, y;
		read(x);
		read(y);
		// scanf("%d%d", &x, &y);
		add(x, y);
		add(y, x);
	}
	dfs(1, 0);
	for (int i = 0; i < m; i++) {
		int a, b, c;
		read(a);
		read(b);
		read(c);
		// scanf("%d%d%d", &a, &b, &c);
		int x = lca(a, b);
		int y = lca(b, c);
		int z = lca(c, a);
		printf("%d %d\n", x ^ y ^ z, d[a] + d[b] + d[c] - d[x] - d[y] - d[z]);
	}
	return 0;
}

题解

询问 a, b, c
x = lca(a, b)
y = lca(b, c)
z = lca(c, a)

集合点： x ^ y ^ z
总路程： d[a] + d[b] + d[c] - d[x] - d[y] - d[z]

P5838 [USACO19DEC]Milk Visits G

https://www.luogu.com.cn/problem/P5838

题目描述

Farmer John 计划建造 NN 个农场，用 N−1N-1 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为 11 到 NN 之间的一个整数 TiT_i。

Farmer John 的 MM 个朋友经常前来拜访他。在朋友 ii 拜访之时，Farmer John 会与他的朋友沿着从农场 AiA_i 到农场 BiB_i 之间的唯一路径行走（可能有 Ai=BiA_i = B_i）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的每个朋友都只喝某种特定品种的奶牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

输入格式

输入的第一行包含两个整数 NN 和 MM。

第二行包含 NN 个空格分隔的整数 T1,T2,…,TNT_1,T_2,\ldots, T_N。第 ii 个农场内的奶牛的品种用 TiT_i 表示。

以下 N−1N-1 行，每行包含两个不同的整数 XX 和 YY（1≤X,Y≤N1 \leq X, Y \leq N），表示农场 XX 与 YY 之间有一条边。

以下 MM 行，每行包含整数 AiA_i，BiB_i，以及CiC_i。AiA_i 和 BiB_i 表示朋友 ii 拜访时行走的路径的端点，CiC_i（1≤Ci≤N1\le C_i\le N）表示这个朋友喜欢的牛奶的奶牛品种。

输出格式

输出一个长为 MM 的二进制字符串。如果第 ii 个朋友会感到高兴，则字符串的第 ii 个字符为 1，否则为 0。

样例 #1

样例输入 #1
5 5
1 1 2 1 2
1 2
2 3
2 4
1 5
1 4 1
1 4 2
1 3 2
1 3 1
5 5 1
样例输出 #1
10110

样例 #2

样例输入 #2
6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4
样例输出 #2
0110

提示

测试点性质：

测试点 22 为以下第二个样例。

测试点 33 满足 N≤103N\le 10^3，M≤2⋅103M\le 2\cdot 10^3。

测试点 4∼74\sim 7 满足 Ci≤10C_i\le 10。

对于 100%100\% 的数据，1≤N≤1051 \leq N \leq 10^5，1≤M≤1051 \leq M \leq 10^5。

供题：Spencer Compton

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int cl[100020];
vector<int> cc[100020];
vector<int> a[100020];
int f[100020][20];
int c[100020];
int d[100020];
int L[100020];
int R[100020];
int s[100020], ss;
char z[100020];
vector<pair<pair<int, int>, int> > q[100020];
void change(int x, int y)
{
	for (; x <= n; x += x & -x)
	{
		c[x] += y;
	}
}
int query(int x)
{
	int re = 0;
	for (; x > 0; x -= x & -x)
	{
		re += c[x];
	}
	return re;
}
void dfs(int x, int y)
{
	L[x] = ss;
	s[ss++] = x;
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 20; i++)
	{
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int i : a[x])
	{
		if (i != y)
		{
			dfs(i, x);
		}
	}
	R[x] = ss;
}
int lca(int x, int y)
{
	if (d[x] < d[y])
	{
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++)
	{
		if (dd >> i & 1)
		{
			x = f[x][i];
		}
	}
	if (x == y)
	{
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--)
	{
		if (f[x][i] != f[y][i])
		{
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main()
{
	ss = 1;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &cl[i]);
		cc[cl[i]].push_back(i);
	}
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 0; i < m; i++)
	{
		int x, y, o;
		scanf("%d%d%d", &x, &y, &o);
		q[o].push_back(make_pair(make_pair(x, y), i));
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < cc[i].size(); j++)
		{
			change(L[cc[i][j]], 1);
			change(R[cc[i][j]], -1);
		}
		for (int j = 0; j < q[i].size(); j++)
		{
			int x = q[i][j].first.first;
			int y = q[i][j].first.second;
			int l = lca(x, y);
			int cnt = query(L[x]) + query(L[y]) - 2 * query(L[l]) + (cl[l] == i);
			z[q[i][j].second] = (cnt > 0) + '0';
		}
		for (int j = 0; j < cc[i].size(); j++)
		{
			change(L[cc[i][j]], -1);
			change(R[cc[i][j]], 1);
		}
	}
	printf("%s\n", z);
	return 0;
}

题解

P6098 [USACO19FEB]Cow Land G

https://www.luogu.com.cn/problem/P6098

题目背景

Cow Land 是一个特殊的奶牛游乐园，奶牛们可以在那里漫步，吃美味的草，并参观不同的景点（尤其过山车特别受欢迎）。

题目描述

Cow Land 总共有 NN 个不同的景点（ 2≤N≤1052 \leq N \leq 10^5 ）。 一共有 n−1n-1 条道路连接任意两个景点，这意味着任意两个景点间只有一条简单路径。

每个景点 ii 都有一个享受值 eie_i ，这个值可能会改变。因为一些景点在早上更有吸引力，而其他景点在下午则更能吸引游客。

从景点 ii 到景点 jj 的奶牛们可以欣赏从景点 ii 到景点 jj 的路上的所有景观。这条路线的享受值为景点 ii 到景点 jj 的路上的所有景点（包括景点 ii 和景点 jj ）的享受值按位进行异或运算的结果。

请帮助奶牛确定他们前往 Cow Land 旅行时计划的路线的享受值。

输入格式

输入的第一行包含两个整数， N,QN,Q（1≤Q≤1051 \leq Q \leq 10^5）。

接下来一行包含 NN 个整数，其中第 ii 个整数 eie_i 代表景点 ii 的享受值。

接下来 N−1N-1 行，每行包含两个整数 a,ba,b ，表示景点 aa 和景点 bb 之间有一条道路相连。

最后 QQ 行，每行包含 3 个整数，表示一个操作，具体内容如下：

  1. 1 i v，表示将 eie_i 修改为 vv 。
  2. 2 i j，表示询问从景点 ii 到景点 jj 的路线的享受值为多少。

输出格式

对于每个 2 操作，输出对应查询的结果。

样例 #1

样例输入 #1
5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3
样例输出 #1
21
20
4
20

提示

子任务：对于 50%50\% 的数据，没有修改操作。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<int> a[100020];
int f[100020][20];
int d[100020];
int c[200020];
int w[100020];
int L[100020];
int R[100020];
int ss = 1;
void change(int x, int y) {
	for (int i = x; i <= 2 * n; i += i & -i) {
		c[i] ^= y;
	}
}
int query(int x) {
	int re = 0;
	for (int i = x; i > 0; i -= i & -i) {
		re ^= c[i];
	}
	return re;
}
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	L[x] = ss;
	ss++;
	for (int i: a[x]) {
		if (i != y) {
			dfs(i, x);
		}
	}
	R[x] = ss;
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 1; i <= n; i++) {
		change(L[i], w[i]);
		change(R[i], w[i]);
	}
	for (int i = 0; i < q; i++) {
		int o, x, y;
		cin >> o >> x >> y;
		if (o == 1) {
			change(L[x], w[x] ^ y);
			change(R[x], w[x] ^ y);
			w[x] = y;
		} else {
			cout << (query(L[x]) ^ query(L[y]) ^ w[lca(x, y)]) << endl;
		}
	}
	return 0;
}

题解

用来和树状数组配合的是进出栈序
有两种使用方法

修改单点，询问子树和
把点权放在第一次出现的位置上
子树和就是区间和

修改单点，询问根节点到某节点的路径和
在第一次出现的位置上加上点权
在第二次出现的位置上减去点权
1 2 2 3 4 4 5 5 3 1

实际实现的时候，可以第二次出现位置不+1
0 1 2 3 4 5 6
1 1
2 2
3 3
4 4
5 5

0 1 2 3 4 5 6 7 8 9 10
1 1
2 2
3 3
4 4
5 5

DFS order and Binary Indexed Tree

5
1 2
1 3
3 4
3 5

 1 3 4 4 5 5 3 2 2 1
 + + + - + - - + - -
[ ]

+w[1] +w[3] +w[4] -w[4] +w[5] = + w[1] + w[3] + w[5] 
from start to L[x]   is from x to the root
+ - can be changed to xor (the operation must be invertible)

two usages of DFS order.
1. increase at first occurence, decrease at last occurence, prefix = path to root
2. only increase at first occurence, subtree = interval


to query the path from a vertex to root
1. DFS order
2. Tree Decomposition

Tree Decomposition
The number of chains are the number of leafs
For any two vertices, we want minize the number of chains between them


 heavy-light decomposition O(log(n))
 longest decomposition.  O(sqrt(n))

Segment tree is a superset of binary indexed tree, except 2D version.

http://www.usaco.org/current/data/sol_cowland_gold_feb19.html

This solution is weird, it uses tree decomposition to maintain the path to root.

but use another binary lifting

http://www.usaco.org/index.php?page=viewproblem2&cpid=948

Tree Boxes

P3128 [USACO15DEC]Max Flow P

https://www.luogu.com.cn/problem/P3128

题目描述

Farmer John has installed a new system of N−1N-1 pipes to transport milk between the NN stalls in his barn (2≤N≤50,0002 \leq N \leq 50,000), conveniently numbered 1…N1 \ldots N. Each pipe connects a pair of stalls, and all stalls are connected to each-other via paths of pipes.

FJ is pumping milk between KK pairs of stalls (1≤K≤100,0001 \leq K \leq 100,000). For the iith such pair, you are told two stalls sis_i and tit_i, endpoints of a path along which milk is being pumped at a unit rate. FJ is concerned that some stalls might end up overwhelmed with all the milk being pumped through them, since a stall can serve as a waypoint along many of the KK paths along which milk is being pumped. Please help him determine the maximum amount of milk being pumped through any stall. If milk is being pumped along a path from sis_i to tit_i, then it counts as being pumped through the endpoint stalls sis_i and

tit_i, as well as through every stall along the path between them.

FJ给他的牛棚的N(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。

FJ有K(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。

输入格式

The first line of the input contains NN and KK.

The next N−1N-1 lines each contain two integers xx and yy (x≠yx \ne y) describing a pipe

between stalls xx and yy.

The next KK lines each contain two integers ss and tt describing the endpoint

stalls of a path through which milk is being pumped.

输出格式

An integer specifying the maximum amount of milk pumped through any stall in the

barn.

样例 #1

样例输入 #1
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
样例输出 #1
9

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[50020];
int f[50020][16];
int d[50020];
int s[50020];
int ans;
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 16; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int i: a[x]) {
		if (i != y) {
			dfs(i, x);
		}
	}
}
int dfs2(int x, int y) {
	int re = s[x];
	for (int i: a[x]) {
		if (i != y) {
			re += dfs2(i, x);
		}
	}
	ans = max(ans, re);
	return re;
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 16; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 16 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		int l = lca(x, y);
		s[x]++;
		s[y]++;
		s[l]--;
		s[f[l][0]]--;
	}
	dfs2(1, 0);
	printf("%d\n", ans);
	return 0;
}

题解

Difference and prefix sum
树上差分

CF191C Fools and Roads

https://codeforces.com/problemset/problem/191/C
https://www.luogu.com.cn/problem/CF191C

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int> > a[100020];
int f[100020][17];
int d[100020];
int s[100020];
int z[100020];
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	for (int i = 1; i < 17; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (pair<int, int> i: a[x]) {
		if (i.first != y) {
			dfs(i.first, x);
		}
	}
}
int dfs2(int x, int y) {
	int re = s[x];
	for (pair<int, int> i: a[x]) {
		if (i.first != y) {
			z[i.second] = dfs2(i.first, x);
			re += z[i.second];
		}
	}
	return re;
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 17; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 17 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(make_pair(y, i));
		a[y].push_back(make_pair(x, i));
	}
	dfs(1, 0);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		int l = lca(x, y);
		s[x]++;
		s[y]++;
		s[l]--;
		s[l]--;
	}
	dfs2(1, 0);
	for (int i = 1; i < n; i++)
	{
		printf("%d%c", z[i], i == n - 1 ? '\n' : ' ');
	}
	return 0;
}

题解

difference and prefix sum on a tree

CF519E A and B and Lecture Rooms

https://codeforces.com/problemset/problem/519/E
https://www.luogu.com.cn/problem/CF519E

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[500020];
int f[500020][20];
int d[500020];
int s[500020];
void dfs(int x, int y) {
	f[x][0] = y;
	d[x] = d[y] + 1;
	s[x] = 1;
	for (int i = 1; i < 20; i++) {
		f[x][i] = f[f[x][i - 1]][i - 1];
	}
	for (int i: a[x]) {
		if (i != y) {
			dfs(i, x);
			s[x] += s[i];
		}
	}
}
int lca(int x, int y) {
	if (d[x] < d[y]) {
		swap(x, y);
	}
	int dd = d[x] - d[y];
	for (int i = 0; i < 20; i++) {
		if (dd >> i & 1) {
			x = f[x][i];
		}
	}
	if (x == y) {
		return x;
	}
	for (int i = 20 - 1; i >= 0; i--) {
		if (f[x][i] != f[y][i]) {
			x = f[x][i];
			y = f[y][i];
		}
	}
	return f[x][0];
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
		a[y].push_back(x);
	}
	dfs(1, 0);
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		if (x == y) {
			printf("%d\n", n);
		} else if (d[x] == d[y]) {
			for (int i = 20 - 1; i >= 0; i--) {
				if (f[x][i] != f[y][i]) {
					x = f[x][i];
					y = f[y][i];
				}
			}
			printf("%d\n", n - s[x] - s[y]);
		} else {
			int dd = d[x] + d[y] - 2 * d[lca(x, y)];
			if (dd & 1) {
				printf("0\n");
			} else {
				if (d[x] < d[y]) {
					swap(x, y);
				}
				dd = dd / 2 - 1;
				for (int i = 0; i < 20; i++) {
					if (dd >> i & 1) {
						x = f[x][i];
					}
				}
				printf("%d\n", s[f[x][0]] - s[x]);
			}
		}
	}
	return 0;
}

题解

Find the midpoint

CF609E Minimum spanning tree for each edge

https://codeforces.com/problemset/problem/609/E
https://www.luogu.com.cn/problem/CF609E

参考代码

题解

Find the maximum edge on a path in the tree

CF176E Archaeology

https://codeforces.com/problemset/problem/176/E
https://www.luogu.com.cn/problem/CF176E

参考代码

题解

Find total length of the subtree

CF1328E Tree Queries

https://codeforces.com/problemset/problem/1328/E
https://www.luogu.com.cn/problem/CF1328E

参考代码

题解

use dfs order to judge ancestor

O(1) judge whether x is an ancestor of y (by DFS order)

If interval x contains interval y, then x is an ancestor of y.

https://www.luogu.com.cn/problem/SP3978

https://www.luogu.com.cn/problem/SP14932

P4427 [BJOI2018]求和

P5002 专心OI - 找祖先

自己有大小为a, b, c的三个子树
那么自己的答案是

(1 * a + (1 + a) * b + (1 + a + b) * c) * 2 + 1

(1 + a + b + c) * (1 + a + b + c) - a * a - b * b - c * c

CF1328E Tree Queries

每个点跳到自己的父亲节点
链越长越好/从跟节点连到最深的节点最好
其他节点必须是最深的节点的祖先，否则NO

所有点进栈最靠后的位置 <= 所有点出栈最靠前的位置 那么YES

判断x和y是什么关系

  1. x和y相同
  2. x是y的祖先
  3. y是x的祖先
  4. x和y没有关系

做法
5
1 2
1 3
3 4
3 5

Codechef ALLIANCE

对于每个帮派求LCA。

对于询问的联盟求LCA，有三个情况。

  1. 联盟的LCA和首都并不是祖先关系，直接计算距离。
  2. 是祖先关系，并且首都下面也有，距离为00。
  3. 倍增向上跳，找到第一次相遇的地方。

spoj POLICEMEN

  1. Lowest Common Ancestor 最近公共祖先
    1. 2 ways to brute forces, find LCA(x, y) 2种暴力方式
      1. P3379 【模板】最近公共祖先（LCA）
      2. P5836 [USACO19DEC]Milk Visits S
      3. P6098 [USACO19FEB]Cow Land G
      4. P4374 [USACO18OPEN]Disruption P
      5. P3128 [USACO15DEC]Max Flow P
      6. P4281 [AHOI2008]紧急集合 / 聚会
      7. P5838 [USACO19DEC]Milk Visits G
      8. P6098 [USACO19FEB]Cow Land G
      9. P3128 [USACO15DEC]Max Flow P
      10. CF191C Fools and Roads
      11. CF519E A and B and Lecture Rooms
      12. CF609E Minimum spanning tree for each edge
      13. CF176E Archaeology
      14. CF1328E Tree Queries
      15. P4427 [BJOI2018]求和
      16. P5002 专心OI - 找祖先
      17. CF1328E Tree Queries
    2. Codechef ALLIANCE
    3. spoj POLICEMEN
≡