题目描述
这个游戏会给出你一棵树，这棵树有NN个节点，根结点是RR，系统会选中MM个点P_1,P_2...P_MP
1
,P
2
...P
M
，要Imakf回答有多少组点对(u_i,v_i)(u
i
,v
i
)的最近公共祖先是P_iP
i
。Imakf是个小蒟蒻，他就算学了LCA也做不出，于是只好求助您了。
Imakf毕竟学过一点OI,所以他允许您把答案模 (10^9+7)(10
9
+7)
输入格式
第一行 N , R , MN,R,M
此后N-1N−1行 每行两个数a,ba,b 表示a,ba,b之间有一条边
此后11行 MM个数 表示P_iP
i
输出格式
MM行，每行一个数，第ii行的数表示有多少组点对(u_i,v_i)(u
i
,v
i
)的最近公共祖先是P_iP
i
容斥原理
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+10,M=2*N,mod=1e9+7;
int next[M],head[N],go[M],tot;
inline void add(int u,int v){
next[++tot]=head[u];head[u]=tot;go[tot]=v;
next[++tot]=head[v];head[v]=tot;go[tot]=u;
}
int size[N],ans[N];
inline void dfs(int u,int fa){
size[u]=1;
for(int i=head[u];i;i=next[i]){
int v=go[i];
if(v==fa)continue;
dfs(v,u);
size[u]+=size[v];
}
ans[u]=size[u];
for(int i=head[u];i;i=next[i]){
int v=go[i];
if(v==fa)continue;
ans[u]+=size[v]*(size[u]-size[v]);
}
}
int main(){
int n,r,m;
cin>>n>>r>>m;
for(int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v);
}
dfs(r,r);
while(m--){
int u;
scanf("%d",&u);
printf("%d
",ans[u]);
}
}