洛谷P4092 [HEOI2016/TJOI2016]树（树链剖分）

思路:显然需要一些树上的数据结构支持我们完成这些蛋疼的操作. 对于这种似乎是树上的问题,可以先试着解决数组的情况 如果这个题是一个数组,就是动态查询一个点最近被染色的前驱嘛. 我们会怎么解决呢?用一个线段树维护下这个区间 [ l , r ] [l,r] [l,r]中最后边被染色的点. 每次查询一个点,就去查询区间 [ 1 , x ] [1,x] [1,x]中最后一个被染色的点就可以了 现在,这个问题被移植到了树上,如果想在树上完成线段树的操作,那么这种数据结构已经呼之欲出了——树链剖分. 使用树链剖分来维护每个链内的最深的被染色的点,对应就是查询区间 [ r t , x ] [rt,x] [rt,x]这个间最深的一个被染色的点. 运用这种思想,小心翼翼地书写树链剖分,线段树部分只需要实现一个点修改,区间查询的功能.而树链剖分的部分,在查询的时候,如果我们在一个段里边找到了答案,就马上返回答案.因为这肯定是最近的那一个,否则就一路往上跳.因为根一定被标记了,不会出现没有解的情况. 代码：（本蒟蒻居然一次过,难见）

/*
You held me down but I broke free,
I found the love inside of me.
Now I don't need a hero to survive
Cause I already saved my life.
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
struct Node{
	int x,y;//
}tree[maxn*4+5];
int tag[maxn*4+5];
#define L (idx=start&&pos=MID+1&&pos=l&&endans.x) ans = tmp;
	}
	return ans;
}
void dfs1(int u,int f){
	depth[u] = depth[f]+1;fa[u] =f;
	sz[u] =1;
	for(auto v : G[u]){
		if(v==f) continue;
		dfs1(v,u);sz[u]+=sz[v];
		if(son[u]==0||sz[son[u]]>n>>m;
	for(int i=1;i>u>>v;
		G[u].pb(v);G[v].pb(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	tr_update(1);
	while(m--){
		char op;cin>>op;
		if(op=='Q'){
			int x;cin>>x;
			cout