P7880 [Ynoi2006] rldcot

给定一棵 $n$ 个节点的树，树根为 $1$，每个点有一个编号，每条边有一个边权。 定义 $dep(x)$ 表示一个点到根简单路径上边权的和，$lca(x,y)$ 表示 $x,y$ 节点在树上的最近公共祖先。 共 $m$ 组询问，每次询问给出 $l,r$，求对于所有点编号的二元组 $(i,j)$ 满足 $l \le i,j \le r$ ，有多少种不同的 $dep( lca(i,j))$。

无

无

Idea：nzhtl1477，Solution：nzhtl1477，Code：lk，Data：nzhtl1477 对于 $10\%$ 的数据，满足 $1\le n,m \le 100$。 对于另外 $20\%$ 的数据，满足 $1\le n,m \le 5000$。 对于另外 $20\%$ 的数据，满足 $1\le n,m \le 50000$。 对于另外 $20\%$ 的数据，满足 $d=1$。 对于 $100\%$ 的数据，满足 $1\le n \le 10^5$，$1\le m \le 5 \times 10^5$，所有数值为整数，$-10^9 \le d \le 10^9$。