$\text{Description}$
有一片景区有 $n$ 个景点，景点间的道路组成一棵 $n$ 个点的树，相邻景点间道路长度相同。有 $m$ 条观光路线，分别位于树上的路径 $(u_1,v_1),(u_2,v_2),\cdots,(u_m,v_m)$，第 $i$ 条观光路线上有 $a_i$ 辆互不相同的车。张三要跟随旅行团来到景区，旅行团的集合区域也是一条路径 $(s,t)$。张三想要依次坐 $K$ 趟车，每次可以选择任意路线上的任意一辆车。我们称景点 $t$ 在路径 $s$ （无论 $s$ 是观光路线还是集合区域）的服务范围内，当且仅当 $t$ 到 $s$ 上任意一点的距离都不超过 $s$ 的长度。称所有在服务范围内的景点的集合为一条路径的服务范围。他希望坐车的方案满足以下要求：
- 乘坐的每辆车所属观光路线的服务范围都包含集合区域的服务范围。
- 任何一个不在集合区域的服务范围内的景点都不会同时在乘坐的每辆车所属观光路线的服务范围内。
张三得知旅行团有 $q$ 套可能的集合区域 $(s_i,t_i)$，他希望你帮他计算出对于每种集合区域的方案，他可能的乘车方案数分别有多少。方案数对 $1000003$ 取模。
$\text{Solution}$
题目给出的所谓的路径，实际上只是生成某一个点集的方法。考虑一条简单路径 $(u,v)$，其长度为 $l$，那么其生成的点集实际上是，以 $(u,v)$ 为直径的最大连通块，证明如下：
首先，$(u,v)$ 上的点显然属于这个点集。
考虑反证，假设该点集存在一条简单路径的长度为 $l’>l$。
设 $l’$ 到 $l$ 的最短距离（即其上任意两点间距离的最小值）为 $d$，对应的 $l$ 上的点为 $u_1$，$l’$ 上的点为 $u_2$，那么 $l$ 上必定存在一个点 $v_1$ 满足 $\operatorname{dis}(u_1,v_1)\ge \frac{l}{2}$，同理 $l’$ 上必定存在一个点 $v_2$ 满足 $\operatorname{dis}(u_2,v_2)\ge \frac{l’}{2}$。那么 $\operatorname{dis}(v_1,v_2)=\operatorname{dis}(v_1,u_1)+\operatorname{dis}(u_1,u_2)+\operatorname{dis}(u_2,v_2)\ge \frac{l+l’}{2}+d>l$，由于 $u_1$ 在 $l$ 上，所以与题设产生矛盾，故 $l$ 为该点集的一条直径。
问题最终可以转换为，给定若干个集合，每个集合有权值，求所有满足条件的取集合的方案中，选取的集合的权值积之和，其中“满足条件”指这 $K$ 个集合的交集为给定的某个集合。
我们设 $S(\odot,d)$ 表示所有到 $\odot$（可能是一个点，也可能是一条边，若为边，则认为其端点到它的距离为 $0$）的距离 $\le \frac{d}{2}$ 的点的集合。可以发现，对于一条路径 $(u,v)$，我们取其中点或者中间的边，那么其生成的点集就是 $S(\odot,d)$，其中 $\odot$ 是中点或者中间的边，$d$ 的就是其长度，证明如下：
假设存在一点 $x\in S(\odot,d)$，那么可知 $\operatorname{dis}(x,\odot)\le \frac{d}{2}$，对于 $(u,v)$ 上的任意一点 $y$ 都满足 $\operatorname{dis}(y,\odot)\le \frac{d}{2}$，则 $\operatorname{dis}(x,y)=\operatorname{dis}(x,\odot)+\operatorname{dis}(y,\odot)\le d$，满足条件。
相反，若 $x\notin S(\odot,d)$，那么可知 $\operatorname{dis}(x,\odot)>\frac{d}{2}$，若取 $u$，则可知 $\operatorname{dis}(x,u)=\operatorname{dis}(x,\odot)+\operatorname{dis}(\odot,u)>d$，不满足条件。
进一步地，我们还有 $S(\odot_1,d_1)\cap S(\odot_2,d_2)$ 也可以表示成 $S(\cdot,\cdot)$ 的形式，证明如下：
待填坑。
值得注意的是，$S(\cdot,\cdot)$ 的个数是 $\mathcal O(n^2)$ 级别的。
至此，想必擅长卷积的各位已经想到了一个卷积的做法，然而它在这里毫无用武之地。
我们考虑另一种方法，即容斥。
设题目给定的集合为 $A_1,A_2,\cdots,A_m$，对应的权值为 $a_1,a_2,\cdots,a_m$。
对于一个集合 $S$ 的答案，为：
既然你都能看到这里了，说明你一定具备看出下一步的实力。
记
有一个事实是，如果若干个集合的交为 $S$，则其一个必要条件是这些集合都是 $S$ 的超集。
这个式子的含义是，对于 $S$ 的任意 $K$ 个超集的权值求积后再求和。我们发现它相比 $G_S$ 多算了一些东西。考虑了一下，我们发现对于某个集合 $S\subsetneq A$，我们算进去了 $G_A$。
故我们有
设 $U$ 为全集，则有 $G_U=F_U$，故我们对集合从大到小依次求出即可。
那么问题就在于，如何求出 $F_S$，然后进一步求出 $G_S$。
这个问题的关键在于利用 $S$ 的性质。
我们先按照题目建出以 $1$ 为根的有根树，然后考虑 $S(\odot,d)$ 的超集 $S(\odot’,d’)$ 有哪些。
由于是有根树，故我们先讨论 $\odot’$ 在 $\odot$ 的子树内的情况。一个显而易见的结论是，$S(\odot’,d’)$ 是 $S(\odot,d)$ 的超集，当且仅当 $\operatorname{dis}(\odot,\odot’)+d\le d’$。我们设 $F_1(\odot,d)$ 表示这个答案，那么先求出 $\odot$ 的子树内，有多少个 $S(\odot’,d’)$ 满足 $d+\operatorname{dis}(\odot,\odot’)=d’$，然后求一个后缀和（因为我们还需要把 $\odot’=\odot$ 的情况算进去，所以我们采用这种合并方法）。这个过程是自底向上的。
其次讨论 $\odot’$ 在 $\odot$ 子树外的情况。我们设 $F_2(\odot,d)$ 表示这个答案。那么这就是换根 DP 的做法，考虑到上面的过程完成后，我们已经求出 $F_2(1,\cdot)$，则自顶向下地求出 $F_2$，同样按照上面的方法，只是不同之处是在求的过程中要用父亲节点的答案减去本身多余的贡献。
至于怎么快速解决自然数 $K$ 次幂，注意到数论函数 $\operatorname{Id}_k(n)=n^k$ 是完全积性函数，我们使用线性筛预处理 $[1,P-1]$ 的 $K$ 次幂，在质数处时使用快速幂计算，其它时候直接相乘，由于质数的级别是 $\mathcal O(\frac{n}{\ln n})$ 的，故该部分时间复杂度为 $\mathcal O(P+P\cdot \frac{\log K}{\log P}+n^2)$，其中 $P=10^6+3$。