Wa #8#9 LCA
查看原帖
Wa #8#9 LCA
110009
Soul_Love楼主2022/11/30 10:17
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,s,h[1000100],l,vis[1000100],f[500010],x[500010],y[500010],z[500010],b[500010],dis[500100];
ll p;
struct edge
{
	int v,next;
}e[2000010];
struct node
{
	ll num;
	int v;
};
vector<node> q[500010];
inline void add(int x,int y)
{
	e[++l].v=y;
	e[l].next=h[x];
	h[x]=l;
}
inline int read()
{
	int k=0,f=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) f|=c=='-';
	for(;isdigit(c);c=getchar()) k=(k<<1)+(k<<3)+(c^48);
	return f?-k:k;
}
inline int find(int x)
{
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
inline void bing(int x,int y)
{
	x=find(x),y=find(y);
	f[y]=x;
}
inline void dfs(int u,int fa)
{
	dis[u]=dis[fa]+1;
	vis[u]=1;
	for(int i=h[u];i;i=e[i].next)
	{
		if(vis[e[i].v]) continue;
		dfs(e[i].v,u);
		bing(u,e[i].v);
	}
	for(int i=0;i<q[u].size();i++)
	{
		if(vis[q[u][i].v])
		{
			b[q[u][i].num]=find(q[u][i].v);
		}
	}
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<n;i++)
	{
		x[1]=read(),y[1]=read();
		add(x[1],y[1]);
		add(y[1],x[1]);
	}
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++)
	{
		x[i]=read(),y[i]=read(),z[i]=read();
		q[x[i]].push_back((node){++p,y[i]});
		q[y[i]].push_back((node){p,x[i]});
		q[x[i]].push_back((node){++p,z[i]});
		q[z[i]].push_back((node){p,x[i]});
		q[y[i]].push_back((node){++p,z[i]});
		q[z[i]].push_back((node){p,y[i]});
	}
	dfs(1,0);
	for(int i=1;i<=p;i+=3)
	{
		ll k1=b[i],k2=b[i+1],k3=b[i+2],ans1=k1,u1=dis[k1],ans2=k1,u2=dis[k1];
		if(u1<dis[k2])
		{
			u1=dis[k2];
			ans1=k2;
		}
		if(u1<dis[k3])
		{
			u1=dis[k3];
			ans1=k3;
		}
		if(u2>dis[k2])
		{
			u2=dis[k2];
			ans2=k2;
		}
		if(u2>dis[k3])
		{
			u2=dis[k3];
			ans2=k3;
		}
		printf("%lld %lld\n",ans1,dis[x[i/3+1]]+dis[y[i/3+1]]+dis[z[i/3+1]]-u1-2*u2);
	}
	return 0;
}
2022/11/30 10:17
加载中...