P6071 『MdOI R1』Treequery

P6071 『MdOI R1』Treequery

简单分讨题。

若 \([l, r]\) 内的点全部在 \(p\) 子树内：

• 考虑找到 \(q = \operatorname{LCA}(l, l + 1, \cdots, r – 1, r)\)，显然 \(q\) 也在 \(p\) 子树内，那么答案为 \(\operatorname{dis}(p, q) = dep_q – dep_p\)。

若 \([l, r]\) 内的点一部分在 \(p\) 子树内，一部分在外面：

• 显然，此时答案为 \(0\)。

否则若 \([l, r]\) 内的点全部都在 \(p\) 子树外：

• 显然我们先应该找到 \(q \in [l, r], \operatorname{LCA}(p, q)\) 中深度最深的那个点 \(q\)。

• 转化一下，即我们只用找到一个点 \(q\)，满足 \(q\) 是 \(p\) 祖先且 \(q\) 子树内包含 \([l, r]\) 中其中一个点即可且是满足这些条件中最深的，可以倍增暴力跳然后判断。

• 然后需要继续特判：若 \(q\) 子树内包含了所有的 \([l, r]\)，那么令 \(R = \operatorname{LCA}(l, l + 1, \cdots, r – 1, r)\)，故 \(R\) 肯定在 \(q\) 子树内，答案为 \(\operatorname{dis}(p, R) = dep_p + dep_R – 2dep_q\)。否则只有一部分在 \(p\) 子树内，其它的在外面，则答案为 \(\operatorname{dis}(p, q) = dep_p – dep_q\)。

然后说一下如何判断 \(p\) 子树内有多少个点在 \([l, r]\) 范围内，考虑差分为 \([1, r] – [1, l – 1]\)，然后只需要考虑前缀；考虑使用主席树，即 \(T_i\) 维护了编号为 \([1, i]\) 的点的时间戳序列，\(T_i \to T_{i + 1}\) 只需要单点修改 \(dfn_{i + 1}\) 即可；查询则在 \(T_r\) 与 \(T_{l – 1}\) 查询区间 \([dfn_p, dfn_p + siz_p – 1]\) 和即可。

哦，还有个查询区间 \(\operatorname{LCA}\)，可以转化为相邻 \(\operatorname{LCA}\) 中深度最小的那个，那么使用 ST 表即可做到单 \(\log\)。

套上倍增，时间复杂度为 \(O(N \log^2 N)\)，空间复杂度为 \(O(N \log N)\)。

link

完整代码：

#include<bits/stdc++.h>
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
const int N = 2e5 + 10, M = 20;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
	if(x < 0){
		putchar('-');
		x = -x;
	}
	if(x > 9)
	  write(x / 10);
	putchar(x % 10 + '0');
}
ll d[N];
int n, q, u, v, w, p, l, r, ans, cnt;
int dfn[N], siz[N], dep[N], top[N], son[N], lg[N], fa[N], rt[N], Fa[M][N];
pair<int, int> F[M][N];
vector<pair<int, int>> E[N];
inline void add(int u, int v, int w){
	E[u].push_back({v, w});
	E[v].push_back({u, w});
}
namespace Seg{
	int node;
	struct Node{
		int lson, rson;
		int sum;
	}X[N * 40];
	inline void newnode(int &k){
		X[++node] = X[k];
		k = node;
	}
	inline void update(int &k, int l, int r, int i){
		newnode(k);
		++X[k].sum;
		if(l == i && i == r)
		  return ;
		int mid = (l + r) >> 1;
		if(i <= mid)
		  update(X[k].lson, l, mid, i);
		else
		  update(X[k].rson, mid + 1, r, i);
	}
	inline int ask(int k, int l, int r, int ql, int qr){
		if(!k)
		  return 0;
		if(l == ql && qr == r)
		  return X[k].sum;
		int mid = (l + r) >> 1;
		if(qr <= mid)
		  return ask(X[k].lson, l, mid, ql, qr);
		else if(ql > mid)
		  return ask(X[k].rson, mid + 1, r, ql, qr);
		else
		  return ask(X[k].lson, l, mid, ql, mid) + ask(X[k].rson, mid + 1, r, mid + 1, qr);
	}
};
inline void dfs1(int u, int f){
	for(int i = 1; i < M; ++i)
	  Fa[i][u] = Fa[i - 1][Fa[i - 1][u]];
	siz[u] = 1;
	for(auto t : E[u]){
		int v = t.fi, w = t.se;
		if(v == f)
		  continue;
		d[v] = d[u] + w;
		dep[v] = dep[u] + 1;
		fa[v] = Fa[0][v] = u;
		dfs1(v, u);
		siz[u] += siz[v];
		if(siz[v] > siz[son[u]])
		  son[u] = v;
	}
}
inline void dfs2(int u, int k){
	dfn[u] = ++cnt;
	top[u] = k;
	if(!son[u])
	  return ;
	dfs2(son[u], k);
	for(auto t : E[u]){
		int v = t.fi;
		if(v == fa[u] || v == son[u])
		  continue;
		dfs2(v, v);
	}
}
inline int lca(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])
		  swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}
inline int LCA(int l, int r){
	if(l == r)
	  return l;
	--r;
	int k = lg[r - l + 1];
	return min(F[k][l], F[k][r - (1 << k) + 1]).se;
}
inline int ASK(int u, int l, int r){
	return Seg::ask(rt[r], 1, n, dfn[u], dfn[u] + siz[u] - 1) - Seg::ask(rt[l - 1], 1, n, dfn[u], dfn[u] + siz[u] - 1);
}
int main(){
//	freopen("A.in", "r", stdin);
//	freopen("A.out", "w", stdout);
	lg[0] = -1;
	n = read(), q = read();
	for(int i = 1; i < n; ++i){
		lg[i] = lg[i >> 1] + 1;
		u = read(), v = read(), w = read();
		add(u, v, w);
	}
	dfs1(1, 1);
	dfs2(1, 1);
	for(int i = 1; i <= n; ++i){
		rt[i] = rt[i - 1];
		Seg::update(rt[i], 1, n, dfn[i]);
	}
	for(int i = 1; i < n; ++i){
		u = lca(i, i + 1);
		F[0][i] = {dep[u], u};
	}
	for(int j = 1; j < M; ++j)
	  for(int i = 1; i + (1 << j) <= n; ++i)
	    F[j][i] = min(F[j - 1][i], F[j - 1][i + (1 << (j - 1))]);
	while(q--){
		p = read() ^ ans, l = read() ^ ans, r = read() ^ ans;
		int now = ASK(p, l, r), all = LCA(l, r);
		if(now == r - l + 1)
		  ans = d[all] - d[p];
		else if(!now){
			int q = p;
			for(int i = M - 1; i >= 0; --i)
			  if(Fa[i][q] && !ASK(Fa[i][q], l, r))
			    q = Fa[i][q];
			q = fa[q];
			now = ASK(q, l, r);
			if(now == r - l + 1)
			  ans = d[all] + d[p] - (d[q] << 1ll);
			else
			  ans = d[p] - d[q];
		}
		else
		  ans = 0;
		write(ans);
		putchar('\n');
	}
	return 0;
}

来源链接：https://www.cnblogs.com/rgw2010/p/18924089