P6071 『MdOI R1』Treequery
P6071 『MdOI R1』Treequery简单分讨题。
若 \(\) 内的点全部在 \(p\) 子树内：
[*]考虑找到 \(q = \operatorname{LCA}(l, l + 1, \cdots, r - 1, r)\)，显然 \(q\) 也在 \(p\) 子树内，那么答案为 \(\operatorname{dis}(p, q) = dep_q - dep_p\)。
若 \(\) 内的点一部分在 \(p\) 子树内，一部分在外面：
[*]显然，此时答案为 \(0\)。
否则若 \(\) 内的点全部都在 \(p\) 子树外：
[*]显然我们先应该找到 \(q \in , \operatorname{LCA}(p, q)\) 中深度最深的那个点 \(q\)。
[*]转化一下，即我们只用找到一个点 \(q\)，满足 \(q\) 是 \(p\) 祖先且 \(q\) 子树内包含 \(\) 中其中一个点即可且是满足这些条件中最深的，可以倍增暴力跳然后判断。
[*]然后需要继续特判：若 \(q\) 子树内包含了所有的 \(\)，那么令 \(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\) 子树内有多少个点在 \(\) 范围内，考虑差分为 \( - \)，然后只需要考虑前缀；考虑使用主席树，即 \(T_i\) 维护了编号为 \(\) 的点的时间戳序列，\(T_i \to T_{i + 1}\) 只需要单点修改 \(dfn_{i + 1}\) 即可；查询则在 \(T_r\) 与 \(T_{l - 1}\) 查询区间 \(\) 和即可。
哦，还有个查询区间 \(\operatorname{LCA}\)，可以转化为相邻 \(\operatorname{LCA}\) 中深度最小的那个，那么使用 ST 表即可做到单 \(\log\)。
套上倍增，时间复杂度为 \(O(N \log^2 N)\)，空间复杂度为 \(O(N \log N)\)。
link
完整代码：
#include#define lowbit(x) x & (-x)#define pi pair#define ls(k) k = '0' && c1; if(i > 1; if(qrmid) return ask(X.rson, mid + 1, r, ql, qr); else return ask(X.lson, l, mid, ql, mid) + ask(X.rson, mid + 1, r, mid + 1, qr); }};inline void dfs1(int u, int f){ for(int i = 1; i < M; ++i) Fa = Fa]; siz = 1; for(auto t : E){ int v = t.fi, w = t.se; if(v == f) continue; d = d + w; dep = dep + 1; fa = Fa = u; dfs1(v, u); siz += siz; if(siz > siz]) son = v; }}inline void dfs2(int u, int k){ dfn = ++cnt; top = k; if(!son) return ; dfs2(son, k); for(auto t : E){ int v = t.fi; if(v == fa || v == son) continue; dfs2(v, v); }}inline int lca(int u, int v){ while(top != top){ if(dep] < dep]) swap(u, v); u = fa]; } return dep < dep ? u : v;}inline int LCA(int l, int r){ if(l == r) return l; --r; int k = lg; return min(F, F + 1; u = read(), v = read(), w = read(); add(u, v, w); } dfs1(1, 1); dfs2(1, 1); for(int i = 1; i 谢谢楼主提供！ 感谢分享，下载保存了，貌似很强大 谢谢分享，辛苦了 懂技术并乐意极积无私分享的人越来越少。珍惜
页:
[1]