求助
查看原帖
求助
112703
与世无争楼主2021/7/28 16:09
#include<cstdio>
#include<vector>
using namespace std;
inline int read() {
	register int n=0;
	register char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') n=n*10+c-'0',c=getchar();
	return n;
}
const int N=500005;
vector <int> v[N],s[N];
int n,m,x,y,z,a,b,ans;
int f[N][20],d[N],l[N],sum[N];
void dfs(int now,int father) {
	sum[now]=1;
	f[now][0]=father;
	d[now]=d[father]+1;
	for (int i=1; i<=l[d[now]]; i++)
		f[now][i]=f[f[now][i-1]][i-1];
	for (int i=0; i<v[now].size(); i++) {
		int k=v[now][i];
		if (k!=father) {
			dfs(k,now);
			sum[now]+=sum[k];
		}
	}
}
int LCA(int x,int y) {
	if (d[x]<d[y]) {
		int a=x;
		x=y;
		y=a;
	}
	while (d[x]>d[y]) x=f[x][l[d[x]-d[y]]-1];
	if (x!=y) {
		for (int i=l[d[x]]; i>=0; i--)
			if (f[x][i]!=f[y][i]) {
				x=f[x][i];
				y=f[y][i];
			}
		return f[x][0];
	} else return x;
}
int main() {
	n=read();
	for (int i=1; i<=n; i++) {
		if ((1<<l[i-1]==i)) l[i]=l[i-1]+1;
		else l[i]=l[i-1];
	}
	m=read();
	for (int i=1; i<n; i++) {
		x=read();
		y=read();
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	while (m--) {
		x=read();
		y=read();
		z=read();
		a=x;
		b=y;
		while (d[x]>d[z]) x=f[x][l[d[x]-d[z]]-1];
		while (d[y]>d[z]) y=f[y][l[d[y]-d[z]]-1];
		if (x!=z&&y!=z) {
			printf("0\n");
			continue;
		}
		if (x==y) {
			x=a;
			y=b;
			while (d[x]>d[z]+1) x=f[x][l[d[x]-d[z]-1]-1];
			while (d[y]>d[z]+1) y=f[y][l[d[y]-d[z]-1]-1];
			ans=n-sum[x]-sum[y];
			if (x==z&&x==1) ans+=sum[x];
			if (y==z&&y==1) ans+=sum[y];
			printf("%d\n",ans);
		} else {
			if (y==z) x=b;
			else x=a;
			while (d[x]>d[z]+1) x=f[x][l[d[x]-d[z]-1]-1];
			printf("%d\n",sum[z]-sum[x]);
		}
	}
	return 0;
}
//By与世无争
  
2021/7/28 16:09
加载中...