Steven_MengのBlog

传送门

不记得是哪场比赛切的题了,发现点$p$的两个不同子树中任选两个点作为$(u_i,v_i)$,他们的$LCA$ 都是$p_i$

所以答案为$\sum_{u,v \in ch[p],u!=v} sz[u]*sz[v]$,剩下容斥乱搞一下就可以了。

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
53
54
55
56
57
58
#include <iostream>
#include <cstdio>
#include <vector>
#define MAXN 10005
#define MOD 1000000007
using namespace std;
struct Edge{
int u,v,nex;
} w[MAXN<<1];
int ecnt,head[MAXN];
inline void add_edge(int u,int v){
w[++ecnt].u=u;
w[ecnt].v=v;
w[ecnt].nex=head[u];
head[u]=ecnt;
}
int sz[MAXN],fa[MAXN];
void dfs(int u,int father){
sz[u]=1;fa[u]=father;
for (register int i=head[u];i;i=w[i].nex){
if (w[i].v!=father){
dfs(w[i].v,u);
sz[u]+=sz[w[i].v];
sz[u]%=MOD;
}
}
}
long long Ans[MAXN];
int main(){
int n,r,m;
scanf("%d%d%d",&n,&r,&m);
for (register int i=1;i<n;++i){
int u,v;
scanf("%d%d",&u,&v);
add_edge(u,v);
add_edge(v,u);
}
dfs(r,-1);
for (register int i=0;i<m;++i){
int u;
scanf("%d",&u);
if (Ans[u]){
printf("%lld\n",Ans[u]);
continue;
}
long long sum1=0,sum2=0;
for (register int i=head[u];i;i=w[i].nex){
if (w[i].v==fa[u]) continue;
sum1+=(long long)sz[w[i].v];
sum2+=((long long)sz[w[i].v]*sz[w[i].v])%MOD;
sum1%=MOD;
sum2%=MOD;
}
long long ret=((sum1*sum1)%MOD-sum2+(long long)sz[u]*2ll%MOD-1ll)%MOD;
printf("%lld\n",ret);
Ans[u]=ret;
}
}

 评论