【树论典题。】P6071 『MdOI R1』Treequery

前言：

输了，被水杯提醒我一直很失败。

正片：

简要题意

求 \([l, r] \to p\) 的路径的交的边权和。

Solution：\(O(n \log^2 n)\) 巨大分讨做法。

考虑分类讨论。

其一，\(p\) 根本就不属于路径上的点，这个求区间 LCA 可以解决 \(p \to anc_{[l, r]}\)

其二，\(p\) 是 \(anc_{l, r}\) 的祖先，显然，还是上面那个。

其三，\(p\) 子树内有 \([l, r]\) 的点，直接为 0 即可，因为这样是没有交的。

其四，\(p \in anc_{l, r}\) 但不属于三，这个考虑倍增，求一个祖先满足三的情况即可。

这些全部都需要子树与区间交的技术，这个直接考虑二维数点，固定编号一维主席树数点即可，这个就是狼人。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define ll long long

// 出题人小黑子树脂 66
using namespace std;

const int _ = 2e5 + 5;

struct EDGE { int y, z; } ;
vector <EDGE> e[_];
int n, q, dfc;
int pa[_][20], son[_], dis[_], dep[_], dfn[_], sz[_], top[_];
int lg[_], st[_][20];
void dfs1 (int x, int fa) {
	dep[x] = dep[fa] + 1, sz[x] = 1;
	pa[x][0] = fa;
	rep(i, 1, 19) pa[x][i] = pa[pa[x][i - 1]][i - 1];
	for (auto & [y, z] : e[x]) {
		if (y == fa) continue ;
		dis[y] = dis[x] + z,
		dfs1(y, x), sz[x] += sz[y];
		if (sz[son[x]] < sz[y]) son[x] = y;
	}
}
void dfs2 (int x, int fa, int anc) {
	dfn[x] = ++ dfc, top[x] = anc;
	if (son[x]) dfs2(son[x], x, anc);
	for (auto & [y, z] : e[x])
		if (y != fa && y != son[x]) dfs2(y, x, y);
}
int queryLCA (int x, int y) {
	while (top[x] != top[y]) {
		if (dep[top[x]] < dep[top[y]]) swap(x, y);
		x = pa[top[x]][0];
	}
	return dep[x] < dep[y] ? x : y;
}
int RangeLCA (int l, int r) {
	int k = lg[r - l + 1];
	return queryLCA(st[l][k], st[r - (1 << k) + 1][k]);
}

int rt[_], tot;
namespace tr {
	struct node {
		int lc, rc, s;
	} t[_ * 25];
	void modify (int & x, int y, int l, int r, int k) {
		x = ++ tot, t[x] = t[y], t[x].s ++;
		if (l == r) return ;
		int mid = (l + r) >> 1;
		if (k <= mid) modify(t[x].lc, t[y].lc, l, mid, k);
		else modify(t[x].rc, t[y].rc, mid + 1, r, k);
	}
	int query (int x, int l, int r, int ql, int qr) {
		if (!x) return 0;
		if (ql <= l && r <= qr) return t[x].s;
		int mid = (l + r) >> 1, ret = 0;
		if (ql <= mid) ret += query(t[x].lc, l, mid, ql, qr);
		if (qr > mid) ret += query(t[x].rc, mid + 1, r, ql, qr);
		return ret;
	}
	int insec (int x, int ql, int qr) {
		return query(rt[qr], 1, n, dfn[x], dfn[x] + sz[x] - 1) -
			   query(rt[ql - 1], 1, n, dfn[x], dfn[x] + sz[x] - 1);
	}
}
void build () {
	dfs1(1, 1), dfs2(1, 0, 1), lg[0] = -1;
	rep(i, 1, n) lg[i] = lg[i >> 1] + 1, st[i][0] = i;
	rep(k, 1, 19) rep(i, 1, n - (1 << k) + 1) 
	st[i][k] = queryLCA(st[i][k - 1], st[i + (1 << k - 1)][k - 1]);
	rep(x, 1, n) tr::modify(rt[x], rt[x - 1], 1, n, dfn[x]);
}
int dist (int x, int y) { return dis[x] + dis[y] - dis[queryLCA(x, y)] * 2; }
int findanc (int x, int l, int r) {
	int p;

	for (int i = 19; i >= 0; i --) {
		int p = pa[x][i];
//		cout << " " << p;
//		if (! p) continue ;
		
		if (! tr::insec(p, l, r)) x = p;
	}
	return pa[x][0];
}
#define bel(x, y) (dfn[x] >= dfn[y] && dfn[x] < sz[y] + dfn[y])
int main () {
	cin >> n >> q;
	rep(i, 1, n - 1) {
		int x, y, z;
		scanf("%d%d%d", & x, & y, & z);
		e[x].push_back({y, z}), e[y].push_back({x, z});
	}
	build();
	int p, l, r, lst = 0;
	while(q --) {
		scanf("%d%d%d", & p, & l, & r);
		p ^= lst, l ^= lst, r ^= lst;
		int anc = RangeLCA(l, r),
			cnt = tr::insec(p, l, r);
		if (bel(anc, p) || !bel(p, anc)) lst = dist(p, anc);
		else if (cnt) lst = 0;
		else {
			int t = findanc(p, l, r);
			lst = dist(p, t);
		}
//		cout << endl;
		printf("%d\n", lst);
	}
	return 0;
}