luogu P5002 专心OI

题目描述

这个游戏会给出你一棵树，这棵树有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\n",ans[u]);

	}

}

巴特西

luogu P5002 专心OI - 找祖先

容斥原理

最新文章

热门文章