『MdOI R1』Treequery

前置知识：主席树，虚数，倍增，最近公共祖先

题目描述

给定一棵 \(n\) 个点的无根树，边有边权。

令 \(E(x,y)\) 表示树上 \(x,y\) 之间的简单路径上的所有边的集合，特别地，当 \(x=y\) 时，\(E(x,y) = \varnothing\)。

你需要实时回答 \(q\) 个询问，每个询问给定 \(p,l,r\)，请你求出集合 \(\bigcap_{i=l}^r E(p,i)\) 中所有边的边权和，即 \(E(p, l\dots r)\) 的交所包含的边的边权和。

通俗的讲，你需要求出 \(p\) 到 \([l,r]\) 内每一个点的简单路径的公共部分长度。

输入格式

第一行两个整数 \(n,q\)，表示树的结点数和询问数。

接下来 \(n-1\) 行，每行三个整数 \(x,y,w\)，表示 \(x\) 与 \(y\) 之间有一条权值为 \(w\) 的边。

接下来 \(q\) 行，每行三个整数 \(p_0,l_0,r_0\)。第 \(i\) 个询问的 \(p,l,r\) 分别为 \(p_0,l_0,r_0\) 异或上 \(lastans\) 的值，其中 \(lastans\) 是上次询问的答案，初始时为 \(0\)。

对于 \(100\%\) 的数据，\(1\leq n,q\leq 2\times 10^5\)，\(1\leq x,y,p\leq n\)，\(1\leq l\leq r\leq n\)，\(1\leq w\leq 10^4\)。

Solution

首先分析一下大概会有哪些情况

\([l\,, r]\)内的节点都在\(p\)的子树之内
- 选择\(p = 1, l = 8, r = 10\)，观察可知此时路径应为\(1 \rightarrow 2\)。
\([l\,,r]\)的节点部分在\(p\)的子树内
- 选择\(p = 1,\,l = 2,\, r = 10\)，观察可知此时答案应该为0。
\([l\,,r]\)的节点都在\(p\)的子树外）
- 如果选择\(p = 9,\,l = 1,\, r = 6\)，此时答案路径为\(6 \rightarrow 9\)
- 如果选择\(p = 9,\,l = 4,\, r = 4\)，此时答案路径为\(2 \rightarrow 6 \rightarrow 9\)，与上一种情况很像，但又似乎不太一样？

再分别深入思考一下

第一种情况，我们能很主观的感觉到答案应为\(lca(l \cdots r) \rightarrow p\)的路径长度。
- 解释：此时我们从p点往下走向\([l \cdots r]\)每一个点，很显然当路径第一次出现分叉（即进入两颗不同的子树）之前的路径应该都是算入答案的，那这个点就是\([l \cdots r]\)这些点的lca，这是符合lca的定义的。
- 做法：那此时我们想知道答案我们只需求出\([l \cdots r]\)的lca，这是在求一个点集的lca
  - 求一个点集的lca：
    
    先假设这个点集的lca为L
    
    想一下dfn序这个东西，一个子树内的dfn序是连续的，可以记录下出点和入点来把一个子树表示成一个区间，那我们考虑这个子树中的一个子树，他的dfn序一定也是连续的，所以子树和子树的子树其实就是区间中的一个小区间，那么这个点集一定是在L的子树内部的，一定可以表示成离散的点或者连续的线段。比方说我们有两个点在下图的1和2区间内，那他们的lca一定是他们外部第一个黄色区间的左端点，所以我们要找到一个点集的lca只要找到这个点集中dfn最小和最大的两个点（即由这些离散的点或者连续的线段形成的区间的最左侧和最右侧区间端点，从而保证外部的第一个大区间一定包含了这个点集，也就是说保证了在L的子树内部）~~纯口胡希望能懂~~
- 所以我们只要把得到点集的最小最大dfn然后求一个lca，那么答案就是\(ans\_situation1 = dis[p \rightarrow lca(\min(dfn[l \cdots r]))), \max(dfn[l\cdots r])]\)
第二种情况的答案是很显然的，必然存在一条走向子树的路径和走向子树之外的路径这两条路径的交集一定为\(\varnothing\)
第三种情况最为复杂