【HZOI/LCA】#C.树

不得不讲，树是一道好题。

先介绍一下题目：

这道题里，求值和改点没有什么好说的，就是换根会很麻烦。

但是大家可以想想，在一个形状固定的树上，无论怎样改变根节点，欧拉序是不变的。

例如：

节点 | 子节点 |

1     | 2 3      |

2     | 4 5      |

3     | 6         |

这样的一棵树，以1为根节点的欧拉序是：1 2 4 2 5 2 1 3 6 3 1

而以3为根节点的欧拉序是：3 6 3 1 2 4 2 5 2 1 3

两个序只有顺序不一样了，各个点的相对位置都没有变。

这也很好理解，因为欧拉序就是绕着树的一个环，环上各点的相对位置是不会跟着环的一个断点的变更而变化的。

修改：新的序中每个点的头位置和末位置恰好包住了在此情况下以这个点为根节点的子树， 这意味着我们只用修改欧拉序中某个点的头位置的值就可以实现整个子树上最小值的修改。

查询：那我们现在求一遍欧拉序，然后把在以某点为根的情况下要求的点的子树的区间求出，即可得出答案。

当然，为了节约空间（次要）以及代码方便（主要），我们可以把欧拉序看做一个环，这样子就能在一个欧拉序内查询了。

下面是主要代码：

#include
using namespace std;
const int z = 131072-32768+2048;
int n, q, r;
int w[z], nowroot, ans;
char ch[2];
int qa, qb, use = 1;

struct EDGE{
	int t, next;
} edge[z];
int cnt, head[z];
void adedge(int &f,int &t) {
	edge[++cnt].next = head[f];
	edge[cnt].t = t;
	head[f] = cnt;
	return;
}

vector node[z];
int ver[4*z];
int tot;
void dfs(int &u) {
	ver[++tot] = w[u];
	node[u].push_back(tot);
	for(int i = head[u];i;i = edge[i].next) {
		dfs(edge[i].t);
		ver[++tot] = 0x7f7f7f;
		node[u].push_back(tot);
	}
	node[u].push_back(tot);
	return;
}

struct TREE{
	int l, r;
	int minn;
} tree[z*8];
#define ld id<<1
#define rd id<<1|1
void construct(int id,int &l,int &r) {
	tree[id].l = l;
	tree[id].r = r;
	if(l == r) {
		tree[id].minn = ver[l];
		return;
	}
	int mid = (l+r)/2;
	construct(ld,l,mid);
	++mid;
	construct(rd,mid,r);
	tree[id].minn = min(tree[ld].minn,tree[rd].minn);
	return;
}
void modify(int id,int &sec,int &val) {
	if(tree[id].l == tree[id].r) {
		tree[id].minn = val;
		return;
	}
	int mid = (tree[id].l+tree[id].r)/2;
	if(sec <= mid) modify(ld,sec,val);
	else modify(rd,sec,val);
	tree[id].minn = min(tree[ld].minn,tree[rd].minn);
	return;
}
int query(int id,int l,int &r) {
	if(tree[id].l == l&&tree[id].r == r) 
		return tree[id].minn;
	int mid = (tree[id].l+tree[id].r)/2;
	if(l > mid) return query(rd,l,r);
	else if(r <= mid) return query(ld,l,r);
	else return min(query(ld,l,mid),query(rd,mid+1,r));
}

int main() {
	scanf("%d %d",&n,&q);
	for(int i = 1;i <= n;++i) {
		int f;
		scanf("%d %d",&f,&w[i]);
		if(f == 0) nowroot = i;
		else adedge(f,i);
	}
	dfs(nowroot);
	construct(use,use,tot);
	for(int i = 1;i <= q;++i) {
		scanf("%s",ch);
		if(ch[0] == 'E') {
			scanf("%d",&nowroot);
		} else if(ch[0] == 'V') {
			scanf("%d %d",&qa,&qb);
			modify(use,node[qa][0],qb);
		} else {
			scanf("%d",&qa);
			if(node[qa][0] < node[nowroot][0]) {
				if(node[qa][node[qa].size()-1] < node[nowroot][0]) {
					ans = query(use,node[qa][0],node[qa][node[qa].size()-1]);
					printf("%d\n",ans);
				} else {
					int tmp, tem;
					for(int i = 0;i < node[qa].size();++i) {
						if(node[qa][i] > node[nowroot][0]) {
							tmp = node[qa][i];
							break;
						}
						tem = node[qa][i];
					}
					ans = min(query(use,use,tem),query(use,tmp,tot));
					printf("%d\n",ans);
				}
			} else if(node[qa][0] > node[nowroot][0]){
				ans = query(use,node[qa][0],node[qa][node[qa].size()-1]);
				printf("%d\n",ans);
			} else {
				ans = query(use,use,tot);
				printf("%d\n",ans);
			}
		}
	}
	return 0;
}