洛谷P4116 Qtree3（树链剖分）

对于多次操作的树上题目,都最好考虑下以下个人发现的一个思路. 1.考虑在数组（一条链）上怎么实现, 2.考虑把数组的情况扩展到树上. 对于方法2,常常会用到树上差分,树链剖分等技巧 对于本题，可以考虑维护一条链上最早出现的那个黑点(深度最浅), 使用树链剖分实现,线段树维护两个值 < x , y > ,表示这一个区间最浅的黑点是 x , 深度为 y x,深度为y x,深度为y. 这代码确实太长了,有一个地方写错都得查找很久

/*
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];
#define L (idxv;
		G[u].pb(v);G[v].pb(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	while(Q--){
		int op;cin>>op;
		if(op==0){
			int x;cin>>x;
			tr_update(x);
		}
		else{
			int x;cin>>x;
			cout