萌新求问
查看原帖
萌新求问
85509
空清虚楼主2021/4/14 22:16
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#define N 100003
using namespace std;
int n,k,x[N],y[N],lg[N],f[N][20],len[N],ans[N],m;
vector<int>ed[N];
queue<int>pt;
bool pa[N];
void dfs(int w,int fa)
{
	f[w][0]=fa,len[w]=len[fa]+1;
	m=max(m,len[w]);
	for (register int i=1;i<=lg[len[w]];++i)
		f[w][i]=f[f[w][i-1]][i-1];
	for (register int i=0;i<ed[w].size();++i)
		if (ed[w][i]!=fa) dfs(ed[w][i],w);
}
int lca(int x,int y)
{
	if (len[x]<len[y]) swap(x,y);
	while (len[x]>len[y])
		x=f[x][lg[len[x]-len[y]]-1];
//	printf("x:%d y:%d\n",x,y);
	if (x==y) return x;
	for (register int i=lg[len[x]]-1;i>=0;--i)
		if (f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
int main()
{
	scanf("%d",&n);
	for (register int i=1;i<n;++i)
	{
		scanf("%d%d",&x[i],&y[i]);
		ed[x[i]].push_back(y[i]);
		ed[y[i]].push_back(x[i]);
	}
	for (register int i=1;i<=n;++i)
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(1,0);
//	cout<<"1:";
//	for (register int i=0;i<ed[1].size();++i)
//		cout<<ed[1][i]<<" ";
//	cout<<"\n";
	scanf("%d",&k);
	for (register int i=1;i<=k;++i)
	{
		int f,t;
		scanf("%d%d",&f,&t);
		ans[f]++;
		ans[t]++;
		ans[lca(f,t)]-=2;
//		printf("%d\n\n",lca(f,t));
	}
//	for (register int i=1;i<=n;++i)
//		printf("%d ",ans[i]);
//	printf("\n\n");
	for (register int i=1;i<=n;++i)
	{
		if (len[i]==m)
		{
//			printf("%d ",i);
			pt.push(i);
			pa[i]=1;
		}
	}
	while (1)
	{
		int pd=pt.front();
		if (pd==1) break;
		pt.pop();
		ans[f[pd][0]]+=ans[pd];
		if (!pa[f[pd][0]])
		{
			pt.push(f[pd][0]);
			pa[f[pd][0]]=1;
		}
	}
//	cout<<"\n";
//	for (register int i=1;i<=n;++i)
//		printf("%d ",ans[i]);
	for (register int i=1;i<n;++i)
	{
		if (len[x[i]]>len[y[i]])
			printf("%d ",ans[x[i]]);
		else
			printf("%d ",ans[y[i]]);
	}
	return 0;
}

第三个点wa,第二条边要求10^5却输出了0.

2021/4/14 22:16
加载中...