Java教程

树的基础

本文主要是介绍树的基础,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

前言

写这个是因为觉得不能颓废了,基础不行就得补

基础之基础

 没啥好说的,看oiwiki
!!!重点是一定要区分无向和有向

树的直径/重心

 发现一个很良心的博客blog。
这模板题也是他出的

树的直径

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LLF LLONG_MAX
const int N=1e6;
struct sss{
	int v,nxt;
	ll val;
}T[N<<1];
int head[N];
int tot;
ll ans=-LLF;
ll f[N];
void add(int u,int v,ll w)
{
	T[++tot].v=v;
	T[tot].val=w;
	T[tot].nxt=head[u];
	head[u]=tot;
}
void dfs(int u,int fa)
{
	f[u]=0;
	for(int i=head[u];i;i=T[i].nxt)
	{
		int v=T[i].v;
		if(v==fa)continue;
		dfs(v,u);
		ans=max(ans,f[u]+f[v]+T[i].val);
		f[u]=max(f[u],f[v]+T[i].val);
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	int u,v;
	ll w;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%lld",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dfs(1,1);
	printf("%lld",ans);
	return 0;
}
这篇关于树的基础的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!