hdu 2874 (LCA)

虚拟赛的时候，一看是求任意两点的最短路，不管怎么优化都超时，最近做一些树的题目，这是求任意两点到最近公共祖先的距离，先用并差集判断是否联通，联通就求最近公共祖先，先把图建成一棵棵树，

#include
#include
#define N 10010
int father[N],dfs[N],n,vis[N],head[N],num,f[N],ans,dis[N];
struct edge
{
	int st,ed,next,w;
}E[N*2];
void addedge(int x,int y,int w)
{
	E[num].st=x;
	E[num].ed=y;
	E[num].w=w;
	E[num].next=head[x];
	head[x]=num++;
}
int find(int a)
{
	if(f[a]!=a)
		f[a]=find(f[a]);
	return f[a];
}
void dfs1(int u)
{
	int i,v;
	vis[u]=1;
	for(i=head[u];i!=-1;i=E[i].next)
	{
		v=E[i].ed;
		if(vis[v]==1)continue;
		father[v]=u;
		dfs[v]=dfs[u]+1;
		dis[v]=E[i].w;
		dfs1(v);
	}
	if(ansdfs[y])
	{
		sum+=dis[x];
		x=father[x];
	}
	while(dfs[y]>dfs[x])
	{
		sum+=dis[y];
		y=father[y];
	}
	while(x!=y)
	{
		sum+=(dis[x]+dis[y]);
		x=father[x];
		y=father[y];
	}
	return sum;
}
int main()
{
	int i,j,k,x,y,m,ans,w;
	while(scanf("%d%d%d",&n,&m,&k)!=-1)
	{
		memset(head,-1,sizeof(head));
		num=0;
		for(i=1;i<=n;i++)
			f[i]=i;
		for(i=0;i