这道题目也是一遍过啊，看着大家怎么都没A的样子，身为首A，发个题解。

题意

求一个点是多少对点的LCA。

思路

这怕是整个题单里与LCA最没关系的题目了……（实际上它应该是想考LCA的概念）

首先，如果两个点[u,v]的LCA是p，那么有两种可能：

1. u=p，v是p的儿子。
2. u，v是p的儿子且不在同一个分支。

对于第1种可能，有size[p]-1种，第二种则直接遍历所有子树，ret累加乘积。

这个题目按理说就A了，结果我又看到了tips。

ber，[1,1]也算的吗？[1,2]和[2,1]你算两种？

那没事，就把父亲是p的情况改为2*size[p]-1，刚好第二种情况还不用除以二了。

结果一看数据范围，差点一口气没喘过来原地升天，n才10000，你m有50000啊？详细计算了一下时间，发现不加记忆化会逝……

谁出的题目这么逆天啊……

#include<iostream>
#include<vector> 
#define N int(2e4)
using namespace std;
vector<int>a[N];//邻接表 
int ts[N],ftr[N],ans[N];//tree_size,father,answer 
void DFS(int u,int f){
	ts[u]=1;//不管怎么样也有1的大小 
	for(int v:a[u]){
		if(v-f){
			ftr[v]=u; 
			DFS(v,u);//先Dfs再求tree_size！ 
			ts[u]+=ts[v];
		}
	}
}
int Query(int p){
	if(ans[p]){//记忆化 
		return ans[p];
	}
	int ret=2*ts[p]-1;//第一种情况 
	for(int u:a[p]){//强行 
		for(int v:a[p]){//遍历 
			if(u!=ftr[p]&&v!=ftr[p]&&u!=v){//防止两子树相同或者找爸行为 
				ret+=ts[u]*ts[v];//第二种情况 
			}
		}
	}
	ans[p]=ret;//记忆化 
	return ret;
}
int main(){
	int n,r,m;
	cin>>n>>r>>m;
	for(int i=1;i<=n-1;i++){
		int a_,b_;
		cin>>a_>>b_;
		a[a_].push_back(b_);
		a[b_].push_back(a_);
	}
	DFS(r,0);//预处理 
	while(m--){
		int p;
		cin>>p;
		cout<<Query(p)<<'\n';
	}
	return 0;//perfect~ 
}