Steven_Meng's Blog

传送门

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

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

#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;
	}
}