这题lca加最大生成树可以吗

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn=1e5+10;

int a1,b1,c1,n,cnt,cnt1,t,sum,head[maxn],fa[maxn],dep[maxn];
int f[maxn][30],g[maxn][30];
struct edge
{
	int u,v,dis1;
}e[4*maxn];
struct node
{
	int next,to,dis;
}a[4*maxn];

int find(int x)
{
	return fa[x]==x ? x : fa[x]=find(fa[x]);
}

bool cmp(edge x,edge y)
{
	return x.dis1>y.dis1;
}

void add(int from,int to,int dis)
{
	a[++cnt].next=head[from];
	a[cnt].to=to;
	a[cnt].dis=dis;
	head[from]=cnt;
}

void dfs(int u1,int fu,int w)
{
	dep[u1]=dep[fu]+1;
	f[u1][0]=fu;
	g[u1][0]=w;
	for(int i=1;i<=20;i++)
	{
		f[u1][i]=f[ f[u1][i-1] ][i-1];
		g[u1][i]=g[ f[u1][i-1] ][i-1]+g[u1][i-1];
		//cout<<u1<<" "<<i-1<<" "<<g[u1][i-1]<<endl;
	}
	for(int i=head[u1];i;i=a[i].next)
	{
		int v1=a[i].to;
		if(v1!=fu) dfs(v1,u1,a[i].dis);
	}
}

int lca(int x,int y)
{
	int ans=0;
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20;i>=0;i--)
	{
		if(dep[f[x][i]]>=dep[y])
		{
			ans+=g[x][i];
			x=f[x][i];
		}
		if(x==y) return ans;
	}
	for(int i=20;i>=0;i--)
	{
		if(f[x][i]!=f[y][i])
		{
			ans+=g[x][i];
			ans+=g[y][i];
			x=f[x][i];
			y=f[y][i];
		}
	}
	return ans+g[x][0]+g[y][0];
}

void k()
{
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=cnt1;i++)
	{
		int f1=find(e[i].u), f2=find(e[i].v);
		if(f1!=f2)
		{
			fa[f1]=f2;
			sum+=e[i].dis1;
			t++;
		}
		if(t==n-1) return ;
	}
}

int main()
{
	while((scanf("%d",&n))==1)
	{
		t=0; sum=0; cnt=0; cnt1=0;
		memset(head,0,sizeof(head));
		memset(dep,0,sizeof(dep));
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		memset(e,0,sizeof(e));
		memset(a,0,sizeof(a));
		
		for(int i=1;i<n;i++)
		{
			scanf("%d%d%d",&a1,&b1,&c1);
			add(a1,b1,c1);
			add(b1,a1,c1);
		}
		dfs(1,0,0);
		//cout<<lca(2,3);
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++)
			{
				//cout<<i<<" "<<j<<" "<<lca(i,j)<<endl;
				e[++cnt1].dis1=lca(i,j);
				e[cnt1].u=i;
				e[cnt1].v=j;
			}
		sort(e+1,e+cnt1+1,cmp);
		//for(int i=1;i<=cnt1;i++)
		//cout<<e[i].dis1<<" ";
		k();
		cout<<sum<<endl;
	}
}