E、Eyjafjalla

题目大意

你有一颗以$11$1为根的$n(1\le n\le 10^5)n(1\backslash le\; n\backslash le\; 10^5)$n(1≤n≤105)个节点的有根树，每个点都有一个温度$t_i(1\le t_i\le 10^9)t\_i(1\backslash le\; t\_i\backslash le\; 10^9)$ti​(1≤ti​≤109)，并且保证每个父亲到儿子的温度一定是递减的。

现在有$Q(1\le Q\le 10^5)Q(1\backslash le\; Q\backslash le10^5)$Q(1≤Q≤105)次询问，每次询问在点$xx$x处有一个耐热性为$[l,r][l,r]$[l,r]的病毒，问它最多可以散播到多少个点，它可以沿着路径向子孙节点也可以向父亲节点传播，当且仅当存在一个温度ti​<l  \mboxor  ti​>r，那么这个$t_{i}t\_i$ti​就不会被传染，并且病毒将在这里被杀死，现在询问最多可以感染多少个节点。

Solution

考点：倍增+dsu+树状数组

我们知道如果对于给出的查询，它不会往上面走就好了，那么这道题就会变得更容易些，这样就变成了我有若干次查询，每次查询某个节点它和它儿子大于$ll$l的有多少个。其实这是非常容易实现的，我们采用倍增的思想，就可以$O(\log n)O(\backslash log\; n)$O(logn)沿着父亲一路向上找到最后一个小于等于$rr$r的节点，然后对于简化后的查询我们有下面的做法。

我们只需要从叶子节点往上$dfsdfs$dfs去维护一个树状数组就可以找到答案，但是很快我们就会发现一个新的问题，我们有了一棵树假设有$1\to 2,1\to 31\backslash to\; 2,1\backslash to3$1→2,1→3，那么我们怎么在计算$33$3的子树答案的时候把$22$2这颗子树带来的贡献屏蔽到呢？主席树？这当然是能做的，也是标答给出的答案，不过我觉得还是接着用之前的树状数组实现比较简单，稍微提一下用主席树如何处理这个问题，我们对于每个节点和它子树构成的区间打上时间戳，接下来就变成了一个可持久化区间查询大于$ll$l的数，用主席树就可以维护出来了。

但是我就不想用主席树怎么办呢？有另外一个应对树上离线查询很好的方法，就是树上启发式合并 (dsu)，它能在$O(n\log n)O(n\backslash log\; n)$O(nlogn)的时间应对树上的离线问题，它最广为人知的做法是求解$QQ$Q次树上查询点$uu$u和它子树里面不同的颜色次数有多少种，那么对应到我们这道题，不就是查询$uu$u和它子树里面大于$ll$l的有多少个吗？我们可以离散之后用树状数组$O(\log n)O(\backslash log\; n)$O(logn)求解。

那么本题总的时间复杂度就是$O(n\log n\log n)O(n\backslash log\; n\backslash log\; n)$O(nlognlogn)，这道题好像直接线段树暴力乱搞都能过，应该是数据偏弱了。

放一个线段树暴力查询时间戳的代码。

if (L <= l && r <= R) {
    if (mini[rt] >= v)	return 0;
    if (maxi[rt] < v)	return r - l + 1;
}

下面就是启发式合并的代码，个人认为挺好的一道启发式合并的题目，和模板挺像的，出题人主要想的还是用主席树维护。

const int N = 1e5 + 7;
ll n, m;
int p[N];

vector<int> G[N];

int fa[N][21], son[N], sz[N];
int a[N], b[N * 4], tot;

void dfs(int u, int father) {
	sz[u] = 1;
	fa[u][0] = father;
	for (int i = 1; i <= 20; ++i) {
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	}
	for (auto& v : G[u]) {
		if (v == father)	continue;
		dfs(v, u);
		sz[u] += sz[v];
		if (son[u] == 0 || sz[son[u]] < son[v])
			son[u] = v;
	}
}

int ans[N];
vector<pai> query[N];
bool vis[N];

inline int Id(int x) {
	return lower_bound(b + 1, b + 1 + tot, x) - b;
}

int c[N];
inline int lowbit(int x) { return x & (-x); }
inline void add(int i, int x) {
	for (; i <= tot; i += lowbit(i))
		c[i] += x;
}
inline int get(int i) {
	int res = 0;
	for (; i; i -= lowbit(i))	res += c[i];
	return res;
}

void calc(int u, int father) {
	add(Id(a[u]), 1);
	for (auto& v : G[u]) {
		if (v == father || vis[v])	continue; // 注意每个节点只能被计算一次别算多了
		calc(v, u);
	}
}

void delte(int u, int father) {
	add(Id(a[u]), -1);
	for (auto& v : G[u]) {
		if (v == father)	continue;
		delte(v, u);
	}
}

void dsu(int u, int father, bool op) {
	for (auto& v : G[u]) {
		if (v != father && v != son[u])
			dsu(v, u, false);
	}
	if (son[u] != 0) {
		dsu(son[u], u, true);
	}
	vis[son[u]] = true;
	calc(u, father);
	for (auto& [id, l] : query[u]) {
		int pos = Id(l);
		ans[id] = sz[u] - get(pos - 1);
	}
	vis[son[u]] = false;
	if (!op)	delte(u, father);
}

int solve() {
	n = read();
	for (int i = 1; i < n; ++i) {
		int u = read(), v = read();
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i)	b[i] = a[i] = read();

	sort(b + 1, b + 1 + n);
	tot = unique(b + 1, b + 1 + n) - (b + 1);

	a[0] = INF64;
	dfs(1, 0);

	m = read();
	for (int i = 1; i <= m; ++i) {
		int x = read(), l = read(), r = read();
		if (a[x] < l || a[x] > r)	ans[i] = 0;
		else {
			for (int k = 20; ~k; --k) {
				if (a[fa[x][k]] <= r)	x = fa[x][k];
			}
			query[x].push_back({ i,l });
		}
	}
	dsu(1, 0, false);

	for (int i = 1; i <= m; ++i)	print(ans[i]);

	return 1;
}