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
完整代码：

[code]#include#define lowbit(x) x & (-x)#define pi pair#define ls(k) k = '0' && c  1;                if(i > 1;                if(qr  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 = Fa[i - 1][Fa[i - 1]];        siz = 1;        for(auto t : E){                int v = t.fi, w = t.se;                if(v == f)                  continue;                d[v] = d + w;                dep[v] = dep + 1;                fa[v] = Fa[0][v] = u;                dfs1(v, u);                siz += siz[v];                if(siz[v] > siz[son])                  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[v]){                if(dep[top] < dep[top[v]])                  swap(u, v);                u = fa[top];        }        return dep < 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 > 1] + 1;                u = read(), v = read(), w = read();                add(u, v, w);        }        dfs1(1, 1);        dfs2(1, 1);        for(int i = 1; i