传送门
不记得是哪场比赛切的题了,发现点p的两个不同子树中任选两个点作为(ui,vi),他们的LCA 都是pi
所以答案为∑u,v∈ch[p],u!=vsz[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; } }
|