P6071『MdOI R1』Treequery是什么？
摘要：讲解 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;
}