洛谷 5002.专心 OI - 找祖先

这题貌似很 naive 呢……
根本不需要取模的说,nn 个数中数对的个数最多是 n2=108n^2 = 10^8 首先,询问 pp,LCA 为 pp 的点对有两种情况:

  • 至少一个为 pp
  • 分别在两棵以 pp不同儿子构成的子树中。

前一种很好理解,后一种若它们在同一棵子树中,很显然可以找到 pp 的一个儿子为更近的祖先。
并且注意点对是区分顺序的。

sizepsize_p 表示以 pp 为根的子树的结点个数,sonpson_p 表示 pp 的儿子的集合,
第一种情况就是 2sizep12size_p - 1,因为 (p,p)(p,p) 重复所以要  1-\ 1
第二种情况,x,ysonp,xysizexsizey\sum\limits_{\forall x,y \in son_p,x \ne y}{size_x \cdot size_y},但是这样还不够优,所以可以优化为 xsonpsizex(sizepsizex1)\sum\limits_{\forall x \in son_p}{size_x \cdot (size_p - size_x - 1)}

此外数据范围显示有可能 m>nm > n,所以我们可以记忆化一下,以免被菊花图询问 mm 次根的毒瘤数据卡掉。

代码:

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
#include <cstdio>
#include <cstring>
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]);
}
}
}