这题貌似很 naive 呢……
根本不需要取模的说，\(n\) 个数中数对的个数最多是 \(n^2 = 10^8\)。 首先，询问 \(p\)，LCA 为 \(p\) 的点对有两种情况： - 至少一个为 \(p\)。 - 分别在两棵以 \(p\) 的不同儿子构成的子树中。
前一种很好理解，后一种若它们在同一棵子树中，很显然可以找到 \(p\) 的一个儿子为更近的祖先。
并且注意点对是区分顺序的。
设 \(size_p\) 表示以 \(p\) 为根的子树的结点个数，\(son_p\) 表示 \(p\) 的儿子的集合，
第一种情况就是 \(2size_p - 1\)，因为 \((p,p)\) 重复所以要 \(-\ 1\)。
第二种情况，\(\sum\limits_{\forall x,y \in son_p,x \ne y}{size_x \cdot size_y}\)，但是这样还不够优，所以可以优化为 \(\sum\limits_{\forall x \in son_p}{size_x \cdot (size_p - size_x - 1)}\)。
此外数据范围显示有可能 \(m > n\)，所以我们可以记忆化一下，以免被菊花图询问 \(m\) 次根的毒瘤数据卡掉。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
const int N = 1e4;
const int mod = 1e9 + 7;
int n,r,m;
int to[(N << 1) + 10],pre[(N << 1) + 10],first[N + 10],ans[N + 10];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v;
pre[tot] = first[u];
first[u] = tot;
}
int q[N + 10],head,tail,sz[N + 10],fa[N + 10];
int main()
{
memset(ans,-1,sizeof ans);
scanf("%d%d%d",&n,&r,&m);
int u,v;
for(register int i = 1;i < n;++i)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
q[++tail] = r;
int p;
while(head < tail)
{
p = q[++head];
sz[p] = 1;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
{
fa[to[i]] = p;
q[++tail] = to[i];
}
}
for(register int i = n;i;--i)
sz[fa[q[i]]] += sz[q[i]];
while(m--)
{
scanf("%d",&p);
if(ans[p] ^ -1)
printf("%d\n",ans[p]);
else
{
ans[p] = ((sz[p] << 1) - 1) % mod;
for(register int i = first[p];i;i = pre[i])
if(to[i] ^ fa[p])
ans[p] = (ans[p] + sz[to[i]] * (sz[p] - sz[to[i]] - 1)) % mod;
printf("%d\n",ans[p]);
}
}
}