講解 P6071 『MdOI R1』Treequery，經過分類討論，使用線段樹，區間 LCA，樹鏈剖分，主席樹等算法數據結構維護。

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;
}