树的直径
树的直径，是指树上最长的一条链。
求树的直径有两种方法
(1.DP)：(d1[u])表示(u)到达子树中叶子节点的最长链,(d2[u])表示(u)到达子树中叶子节点的次长链，两条链不能有交集，只需要对每个节点做以下更新同时维护最大值最小值即可
void dfs1(int u,int fa)
{
for(int i=head[u];i;i=e[i].nxt)
{
int ev=e[i].v;
if(ev==fa) continue;
dfs1(ev,u);
if(d1[ev]+e[i].w>d1[u])
d2[u]=d1[u],d1[u]=d1[ev]+e[i].w;
else if(d1[ev]+e[i].w>d2[u])
d2[u]=d1[ev]+e[i].w,c2[u]=ev;
}
}
这样维护保证了不会出现交集，不用(d2[ev])更新是因为我们找的是最大值，如果(d1[ev])不能跟新(d2[ev])更不能更新，如果前者可以更新再用(d2[ev])更新也没必要了
最后如此统计答案即可
ans=max(d1[i]+d2[i],ans);(1<=i<=n)
(2.)两遍(BFS/DFS)
具体流程：先随意指定一个节点（记为(z)）作为起点搜索到距离起点最远的点，记这个点(x)，从(x)开始搜索到距离(x)最远的点(y)，因为树上路径唯一，(x->y)就是直径
证明：
假设(x)在直径上，因为第一次搜索是找的最远节点，它一定是叶子节点，所以它一定是直径的一端，从(x)找最远距离一定是直径。
所以我们只需要证明(x)一定在直径上即可，考虑反证法，假设(x)不在直径上，而直径真实的端点是(q)
分两种情况考虑：
((1)k)在直径上，对于这种情况，因为第一次找的是最远距离，也就是说(dis(k,x)>dis(k,q))，根据定义，将直径端点换成(x)显然可以使直径更长，这与“直径是最长链”相违背
((2)k)不在直径上
(ecause b+d>d+c+a)
( herefore b>c+a)
( herefore b+c>a)
可以将直径的(a)段换成(b+c)更优
这与“直径是最长链”相违背
综上，我们所说的方法是正确的
树的重心
概念：以树的重心为整棵树的根时，它的最大子树最小（也就是删除该点后最大联通块最小）
用(siz[i])表示以(i)为根的子树的总大小(包括根)
用(mson[i])表示以(i)的最大子树的大小
随便指定一个点(dfs)一下顺便维护上面两个值。
(n-siz[i])就是删去(i)后上方联通块大小，只需要跟(mson[i])取个(max)，就是以该节点为根时最大子树的大小，然后更新答案即可
ans=INF;
void dfs(int u,int fa)
{
siz[u]=1,mson[u]=0;//注意初始化为0，因为有可能没有子树
for(int i=head[u];i;i=e[i].nxt)
{
int ev=e[i].v;
if(ev==fa) continue;
dfs(ev,u);
siz[u]+=siz[ev];
mson[u]=max(mson[u],siz[ev]);
}
ans=min(ans,max(n-siz[u],mson[u]));
}
树的中心
概念：以树的中心为整棵树的根时，从该根到每个叶子节点的最长路径最短
也有两种方法
(1.)树形(DP)
我们需要维护每个点到所有叶子节点的最长距离
前面已经知道了怎么维护每个节点到它的子树中的叶子节点的最长距离和次长距离，考虑怎么维护这个点向上的最远距离
(c1[i])表示(d1[i])从哪个点更新，(c2[i])表示(d2[i])从哪个点更新，用(up[i])表示向上的最远距离。
再用一开始指定的点做一次(DFS)，这次是从根到叶子节点状态转移。
对于每一个点，假设它的父亲的最长链，也就是(d1[fa[u]])不是从它更新来的，那么(up[u]=max(up[fa[u]],d1[fa[u]])+dis[fa[u]][u])
如果的父亲的最长链是从它更新来的，那次长链一定不是从它更新来的，可以看看前面的定义，两条链没有交集，所以
(up[u]=max(up[fa[u]],d2[fa[u]])+dis[fa[u]][u])
最后这样更新答案
ans=min(ans,max(up[i],d1[i]));
直接上完整代码吧
#include<cstdio>
#include<iostream>
#define re register
#define maxn 100010
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct Edge{
int v,w,nxt;
}e[maxn<<2];
int ans,x,y,pos,z;
int n,head[maxn],cnt,d1[maxn],up[maxn],d2[maxn],c1[maxn],c2[maxn];
inline void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs1(int u,int fa)
{
for(int i=head[u];i;i=e[i].nxt)
{
int ev=e[i].v;
if(ev==fa) continue;
dfs1(ev,u);
if(d1[ev]+e[i].w>d1[u])
d2[u]=d1[u],c2[u]=c1[u],d1[u]=d1[ev]+e[i].w,c1[u]=ev;
else if(d1[ev]+e[i].w>d2[u])
d2[u]=d1[ev]+e[i].w,c2[u]=ev;
}
}
void dfs2(int u,int fa)
{
for(int i=head[u];i;i=e[i].nxt)
{
int ev=e[i].v;
if(ev==fa) continue;
if(c1[u]!=ev) up[ev]=max(d1[u],up[u])+e[i].w;//不是从它更新来的
else up[ev]=max(d2[u],up[u])+e[i].w;
dfs2(ev,u);
}
}
int main()
{
n=read();
for(re int i=1;i<n;++i)
{
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
dfs1(1,0);
dfs2(1,0);
ans=0x3f3f3f3f;
for(re int i=1;i<=n;++i)
{
if(max(up[i],d1[i])<ans) ans=max(up[i],d1[i]),pos=i;
}
printf("%d %d",pos,ans);//pos表示中心位置
return 0;
}
(2.)简单(DFS/BFS)
树的中心一定在树的直径上，且趋于中点
这个是比较显然的，如果不在直径上，它的最远距离只会更远
因此我们在找出直径的同时，对于直径的两个端点(pos1,pos2)，分别求到每个点的距离(d1[i],d2[i])
最后对于每个点更新即可
ans=min(ans,max(d1[i],d2[i]));
完整代码
#include<cstdio>
#include<iostream>
#define re register
#define maxn 100010
using namespace std;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct Edge{
int v,w,nxt;
}e[maxn<<2];
int x,y,z;
int pos1,pos2,d[maxn],d1[maxn],d2[maxn];
int n,tmp1,tmp2,tmp3,ans,pos,cnt,head[maxn];
inline void add(int u,int v,int w)
{
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs1(int u,int fa,int dis)
{
for(int i=head[u];i;i=e[i].nxt)
{
int ev=e[i].v;
if(ev==fa) continue;
dfs1(ev,u,dis+e[i].w);
}
d[u]=dis;
if(dis>tmp2) tmp2=dis,tmp1=u;
}
int main()
{
n=read();
for(re int i=1;i<n;++i)
{
x=read(),y=read(),z=read();
add(x,y,z);
add(y,x,z);
}
dfs1(1,0,0);
pos1=tmp1;
tmp2=0,tmp1=0;
dfs1(pos1,0,0);
pos2=tmp1;
tmp2=0,tmp1=0;
//找到直径了
for(re int i=1;i<=n;++i) d1[i]=d[i];
dfs1(pos2,0,0);
for(re int i=1;i<=n;++i) d2[i]=d[i];
ans=0x3f3f3f3f;
for(re int i=1;i<=n;++i)
{
if(ans>max(d1[i],d2[i]))
ans=max(d1[i],d2[i]),pos=i;
}
printf("%d %d",pos,ans);
return 0;
}
最后附一个树的数据生成器
#include<cstdlib>
#include<iostream>
#include<ctime>
#include<cstdio>
#include<algorithm>
#define re register
using namespace std;
int n,q,qx,qy,w;
int x[10010],y[10010],z[10010];
int a[10010],fa[10010];
int cnt2,cnt;
struct Edge{
int u,v,w;
}e[10010];
int find(int x)
{
return fa[x]==x?x:find(fa[x]);
}
int flag;
int main()
{
srand(time(0));
n=rand()%10+1;
printf("%d
",n);
for(re int i=1;i<=n;++i)
{
for(re int j=i+1;j<=n;++j)
{
x[++cnt]=i;
y[cnt]=j;
z[cnt]=rand()%100+1;
}
}
for(re int i=1;i<=cnt;++i) a[i]=i,fa[i]=i;
random_shuffle(a+1,a+cnt+1);
for(re int i=1;i<=cnt;++i)
{
int pos=a[i];
int eu=find(x[pos]),ev=find(y[pos]);
if(eu==ev) continue;
fa[ev]=eu;
e[++cnt2].u=x[pos],e[cnt2].v=y[pos],e[cnt2].w=z[pos];
if(cnt2==n-1) break;
}
for(re int i=1;i<=cnt2;++i)
{
printf("%d %d %d
",e[i].u,e[i].v,e[i].w);
}
return 0;
}