昨天教练问我：你用树剖做这道题，怎么全部清空状态呢？    我：？？？不是懒标记就完了？？？    教练：树剖不是要建很多棵线段树吗，不止log个，你要一个一个清？    我：为什么要建很多棵线段树？不都是一棵树来记录吗？不会还有人树剖每条链都建线段树吧

这里笔者给现在或是以后写树剖的读者们提个建议，写树剖用一个线段树记录足矣，只要保证一条重链上的点在线段树上是按深度连续的（并且一个子树内的点在线段树上是连续的），就不会出问题，好想、好写、还好调

题面

题解

我们可以把问题转换一下，每次就不让mz实质性地扩散状态，而是求距离 x 最近的一开始不理睬的mz距离 x 的距离，这样再判断时间就行，由于每个mz不理睬的起始时间是不一样的，所以我们可以上溯到 0 时刻，求等价的、 0 时刻开始不理睬的最近距离。

举个例子，对于 x ，原本在其上方（来自祖先的方向）的点就等价地往上移动 ti 距离，比如 a 时刻加进来一个与 x 的距离为 b 的mz（在 x 上方，不一定非要是祖先），那么就等价于 0 时刻加进来一个深度为 depth[x] - b - a 的 x 的祖先；

原本在 x 下方（朝向叶子的方向）的点就等价地往下移动 ti 距离，比如 a 时刻加进来一个深度为 b 的mz（在 x 的子树中），那么就等价于 0 时刻加进来一个深度为 b + a 的 x 的后代。

很明显祖先和后代的情况是截然不同的，我们可以分开维护，用树链剖分，在线段树上维护子树和链的最值。

后代方向

对于后代，我们每次加入"一个点的深度+当前时刻"到树上（单点修改），在线段树上维护 sn (Subtree Number) 为该值的最小值（显然这里越小越近），询问的时候访问子树中的 sn 然后再减去 depth[x] 就是子树中最近的距离了。

祖先方向

对于来自祖先方向，就比较复杂。树上比较远的两个点，实际上是要绕过lca才能扩散到的，

我们把右边折上去

相当于从祖先方向跑下来，我们把这个 depth' 减去加进来的时刻，存到 lca 里，维护最大值（这里则是越大越近）。

但是，这么来说，加入一个点 i 的时候，i 的每个祖先都要修改。所以解决方法就是区间修改，每次给一条链（重链的子链）集体加入 depth[i]+time（加入的是在子树中的等价起点了，何如？），线段树里则记录 depth' - time 的最大值，记为 an（Ancestor Number）。所以在线段树里就需要用懒标记维护 an：

懒标记 lza (Lazy mark of Ancestor Number) 记录 depth[i]+time 的最小值，跟 sn 类似，但是记录的是不同的东西。把 lza 重现在 an 里就是这条链中深度最大的点的深度 depth 减去 (lza - depth) ：

void ada(int a,int anc) {//加入anc = depth[i] + time

	tre[a].an = max(tre[a].an,d[id[tre[a].r]] - (anc - d[id[tre[a].r]]));//d 即 depth,id表示线段树上位置对应的原树上节点编号

	tre[a].lza = min(tre[a].lza,anc);

}

用深度最大的点（右端点）更新 an ，是因为这个修改操作特殊点在于，lza 一定大于链上的每一个点的深度，我们是更新 i 的祖先嘛，所以最下面（深度最大）的那个祖先用来更新肯定是最合适的，于是这样就可以维护了 an 了。

询问的时候，只需要 depth[x] - 从 x 到根的链上的 an 就是来自祖先方向的最短距离。

整合

询问点的时候，把上述两个方向求得的距离取最小值，然后减去当前时间，若小于等于 0 则已被扩散到。

对于初始化，需要把 an 赋为 -INF，把 sn 和 lza 赋为 INF。

最后它有一个清空操作，这个在线段树上用一个清空标记就行了，应该很简单的（前提是只建一棵线段树）。

CODE

#include<map>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 100005

#define LL long long

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) ((-x)&(x))

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f=-f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s=getchar();}

	return f*x;

}

const int MOD = 1000000007;

int n,m,i,j,s,o,k;

vector<int> g[MAXN];

int d[MAXN],fa[MAXN],siz[MAXN],son[MAXN],tp[MAXN],dfn[MAXN],cnt,rr[MAXN],id[MAXN];

struct tr{

	int l,r;

	int an,sn;//max,min

	int lza,lzc;//min,---

	tr(){l = r = lzc = 0;sn = lza = 0x3f3f3f3f;an = -0x3f3f3f3f;}

}tre[MAXN<<3];

void maketree(int a,int L,int R) {

	tre[a].l = L;tre[a].r = R;

	if(L < R) {

		int mid = (L + R) >> 1;

		maketree(a<<1,L,mid);

		maketree(a<<1|1,mid+1,R);

	}return ;

}

void upd(int a) {

	tre[a].an = max(tre[a<<1].an,tre[a<<1|1].an);

	tre[a].sn = min(tre[a<<1].sn,tre[a<<1|1].sn);

}

void ada(int a,int anc) {

	tre[a].an = max(tre[a].an,d[id[tre[a].r]] - (anc - d[id[tre[a].r]]));

	tre[a].lza = min(tre[a].lza,anc);

}

void cle(int a) {tre[a].an = -0x3f3f3f3f;tre[a].sn = tre[a].lza = 0x3f3f3f3f;tre[a].lzc = 1;}

void pus(int a) {

	if(tre[a].l == tre[a].r) return ;

	if(tre[a].lzc) {

		cle(a<<1);cle(a<<1|1);

		tre[a].lzc = 0;

	}

	if(tre[a].lza < 0x3f3f3f3f) {

		ada(a<<1,tre[a].lza);

		ada(a<<1|1,tre[a].lza);

		tre[a].lza = 0x3f3f3f3f;

	}

	return ;

}

void adds(int a,int ad,int son) {

	if(tre[a].l > ad || tre[a].r < ad) return ;

	if(tre[a].l == tre[a].r) {tre[a].sn = min(tre[a].sn,son);return ;}

	pus(a);

	adds(a<<1,ad,son);adds(a<<1|1,ad,son);

	upd(a); return ;

}

void adda(int a,int l,int r,int anc) {

	if(tre[a].l > r || tre[a].r < l) return ;

	if(tre[a].l >= l && tre[a].r <= r) {ada(a,anc);return ;}

	pus(a);

	adda(a<<1,l,r,anc);adda(a<<1|1,l,r,anc);

	upd(a); return ;

}

int findsons(int a,int l,int r) {

	if(tre[a].l > r || tre[a].r < l) return 0x3f3f3f3f;

	if(tre[a].l >= l && tre[a].r <= r) {return tre[a].sn;}

	pus(a); return min(findsons(a<<1,l,r),findsons(a<<1|1,l,r));

}

int findance(int a,int l,int r) {

	if(tre[a].l > r || tre[a].r < l) return -0x3f3f3f3f;

	if(tre[a].l >= l && tre[a].r <= r) {return tre[a].an;}

	pus(a); return max(findance(a<<1,l,r),findance(a<<1|1,l,r));

}

//-------------------------------------------

void dfs0(int x) {//d[],fa[],siz[],son[]

	d[x] = d[fa[x]] + 1;

	siz[x] = 1;

	son[x] = 0;

	for(int i = 0;i < (int)g[x].size();i ++) {

		int y = g[x][i];

		if(y != fa[x]) {

			fa[y] = x;

			dfs0(y);

			siz[x] += siz[y];

			if(siz[y] > siz[son[x]]) {

				son[x] = y;

			}

		}

	}return ;

}

void dfs(int x) {//tp[],dfn[],rr[],id[]

	dfn[x] = ++ cnt;

	id[cnt] = x;

	if(son[fa[x]] == x) tp[x] = tp[fa[x]];

	else tp[x] = x;

	if(son[x]) dfs(son[x]);

	for(int i = 0;i < (int)g[x].size();i ++) {

		if(g[x][i] != fa[x] && g[x][i] != son[x]) {

			dfs(g[x][i]);

		}

	}

	rr[x] = cnt;

	return ;

}

void addx(int a,int ti) {

	adds(1,dfn[a],d[a] + ti);

	int fn = tp[a],da = d[a] + ti;

	while(fn) {

		adda(1,dfn[fn],dfn[a],da);

		a = fa[fn];fn = tp[a];

	}

	return ;

}

int query(int a) {

	int dis = findsons(1,dfn[a],rr[a]) - d[a];

	int fn = tp[a],da = d[a];

	while(fn) {

		dis = min(dis,da - findance(1,dfn[fn],dfn[a]));

		a = fa[fn];fn = tp[a];

	}

	return dis;

}

int main() {

	n = read();m = read();

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

		s = read();o = read();

		g[s].push_back(o);

		g[o].push_back(s);

	}

	dfs0(1);

	dfs(1);

	maketree(1,1,cnt);

	int tim = 0;

	while(m --) {

		k = read();s = read();

		if(k == 1) {

			addx(s,tim);

		}

		else if(k == 2) {

			cle(1);

		}

		else if(k == 3) {

			int md = query(s);

			printf((md - tim <= 0) ? "wrxcsd\n":"orzFsYo\n");

		}

		tim ++;

	}

	return 0;

}

2020牛客NOIP赛前集训营-提高组（第三场） C - 牛半仙的妹子Tree （树链剖分）的相关教程结束。