求助
查看原帖
求助
677489
Aaron530楼主2024/10/4 12:32

P3258 松鼠的新家

#include <bits/stdc++.h>
using namespace std;
int n;
int order[300005];
int d[300005],father[300005][25],c[300005];
vector <int> e[300005];
void dfs(int x,int fa)
{
	d[x]=d[fa]+1;
	father[x][0]=fa;
	for(int i=1;i<=19;i++)
		father[x][i]=father[father[x][i-1]][i-1];
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y==fa)
			continue;
		dfs(y,x);
	}
}
int lca(int x,int y)
{
	if(d[x]<d[y])
		swap(x,y);
	for(int i=19;i>=0;i--)
		if(d[y]<=d[father[x][i]])
			x=father[x][i];
	if(x==y)
		return x;
	for(int i=19;i>=0;i--)
		if(father[x][i]!=father[y][i])
			x=father[x][i],y=father[y][i];
	return father[x][0];	
}
void dfs1(int x,int fa)
{
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y==fa)
			continue;
		dfs1(y,x);
		c[x]+=c[y];
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>order[i];
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<n;i++)
	{
		int x=order[i],y=order[i+1];
		int lcaxy=lca(x,y);
		c[x]++;
		c[y]++;
		c[lcaxy]--;
		c[father[lcaxy][0]]--;
	}
	dfs1(1,0);
	for(int i=2;i<=n;i++)
		c[i]--;
	for(int i=1;i<=n;i++)
		cout<<c[i]<<" ";
	return 0;
}

有人可以告诉我这个dfs1函数有什么问题吗

2024/10/4 12:32
加载中...