目录
1.定义 ：
树的直径是树上两点间距离的最大值。即树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链
最长链：4-2-1-7-6-3
所以这颗树的直径是15，直径路径为4-2-1-3-6
2.直径的性质：
直径的性质1：直径的端点一定是叶子节点
直径的性质2：任意点的最长链端点一定是直径端点
直径的性质3：如果一棵树有多条直径且边权都为正，那么它们必然相交，且有极长连续段（可以是一个点，交点为树的中心）
直径的性质4：树T1的直径为x,y，树T2的直径为s,t。现有一边u,v与两颗树相连，新树的直径端点一点是x,y,s,t中的两个
3.树的直径求解方法：
引理性质2：任意点的最长链端点一定是直径端点。方法：我们随意找一个点x,进行dfs找到最长链的端点s,再以端点s做第二遍dfs，此时可以找到直径的第二个端点t。此时端点s到t的距离就是树的直径。
输入一颗无根树，第一行为一个正整数n(n<1e5),表示这颗树有n个节点接下来的n−1行,每行三个正整数u,v,w，表示u,v（u,v<=n）有一条权值为w(w<100)的边相连，求树的直径。
#include<bits/stdc++.h>
using namespace std;
int n,data[100005],pl,maxn;
vector<int> v[100005];
vector<int> w[100005];
void dfs(int x,int fa) {
for(int i=0; i<v[x].size(); i++) {
int y=v[x][i];
if(y==fa) continue;
data[y]=data[x]+w[x][i];
if(data[y]>maxn) maxn=data[y],pl=y;//记录端点
dfs(y,x);
}
}
int main() {
cin>>n;
for(int i=1; i<n; i++) {
int x,y,z;cin>>x>>y>>z;
v[x].push_back(y);
v[y].push_back(x);
w[x].push_back(z);
w[y].push_back(z);
}
dfs(1,0);//寻找直径
memset(data,0,sizeof data);//清空距离
dfs(pl,0);//从pl出发寻找端点
cout<<maxn;
return 0;
}4.直径端点求解方法：
我们通过记录父亲节点的方式能够把直径上的所有点全部记录下来。在树中，直径端点是常用点(假设端点为s,t)，我们树上任意一点p所能到的最大距离，只有可能是到ps或pt
那如何找到所有点到两个直径端点的距离？
朴素方法：
求出直径端点后，以每个点为根做dfs，找到根节点到端点的距离。复杂度O(N2)。
优化方法：
第一次从任意点出发，必然能到达直径的一个端点s。第二次从s点进行dfs找到端点t，此时记录所有点到s的距离。第三次从t点进行dfs，记录所有点到t的距离。复杂度：O(n)
5.例题：
题目描述：
输入一颗无根树，第一行为一个正整数n(n<1e5),表示这颗树有n个节点接下来的n−1行,每行三个正整数u,v,w，表示u,v（u,v<=n）有一条权值为w(w<100)的边相连，输出各个点到左右端点的距离。(默认左端点为编号小的点，右端点为编号大的点。)
题目分析：
我们需要多次求树的直径。通过第一次dfs从根寻找第一个端点pl，再通过第二次dfs从pl寻找第二个端点pr，并记录所经过的距离，最后通过第三次dfs记录每个点到左右端点的距离。多次求树的直径，有很多重复操作，包括清空最长链长度，以及重置距离数组，我们可以放到循环中，这样就不容易遗忘初始化。同时我们还可以记录当前是第几次dfs，到指定次数dfs时才更新信息。
正确代码：
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100002];
vector<int> w[100002];
int n,maxn,sum,data[100002],dl[100002],s[100002],l,r;
void dfs1(int x,int fa) {
if(data[x]>maxn) maxn=data[x],sum=x;
for(int i=0; i<v[x].size(); i++) {
int y=v[x][i];
if(y==fa) continue;
data[y]=data[x]+w[x][i];
dfs1(y,x);
}
}
void dfs2(int x,int fa) {
dl[x]=data[x];
if(data[x]>maxn) maxn=data[x],sum=x;
for(int i=0; i<v[x].size(); i++) {
int y=v[x][i];
if(y==fa) continue;
data[y]=data[x]+w[x][i];
dfs2(y,x);
}
}
void dfs3(int x,int fa) {
s[x]=data[x];
if(data[x]>maxn) maxn=data[x],sum=x;
for(int i=0; i<v[x].size(); i++) {
int y=v[x][i];
if(y==fa) continue;
data[y]=data[x]+w[x][i];
dfs3(y,x);
}
}
int main() {
cin>> n;
for(int i=1; i<n; i++) {
int x,y,z;cin>>x>>y>>z;
v[x].push_back(y);
v[y].push_back(x);
w[x].push_back(z);
w[y].push_back(z);
}
dfs1(1,0);
memset(data,0,sizeof data);
maxn=0,l=sum;
dfs2(l,0);
memset(data,0,sizeof data);
maxn=0,r=sum;
dfs3(r,0);
if(l>r) swap(dl,s),swap(l,r);//保证做端点较小
for(int i=1; i<=n; i++) cout<<i<<" "<<dl[i]<<" "<<s[i]<<endl;
return 0;
}6.直径公共点：
以当一颗树存在多条直径时，引理性质3，公共边一定连续，因此可以直接对公共点/边进行求解
公共点公共边的求法：
找到直径左右端点s,t，从左往右遍历直径上的点进行dfs，如果某点r在直径外找到一点与到右端点t距离相同，点r右边的点一定不是公共点。同理，从右往左遍历直径上的点进行dfs，如果某点l在直径外找到一点与到左端点s距离相同，l左边的点一定不是公共点。此时，l->r就是我们直径的公共点。因此我们只需要找到公共点边界l,r即可。使得l尽可能靠右，r尽可能靠左。
7.例题：
题目描述：
给定一棵树，树中包含 n（n<=1e5）个结点（编号1~n）和 n−1 条无向边，每条点都有一个权值c（1<=c<=100）。请找出所有直径的公共点权值和。(第一个点权值为0)
题目分析：
按照直径公共点求解的方法进行操作。
1.找到直径左右端点lp,rp;
2.找到直径上的点x到左端点lp的距离ld[x]，到右端点rp的距离rd[x];
3.找到直径上的点x到非直径点(且不通过直径点)的距离dis[x]
4.从直径左端点开始向右端点扫描，如果dis[i]=rd[i]，则停下，找到公共点右区间r=i
5.从直径右端点开始向左端点扫描，如果dis[j]=ld[j]，则停下，找到公共点左区间l=j
6.计算直径上i到j的点权和得出答案。
真确代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2E5+5;
int n,c[N];
vector<int> v[N];
int dl[N],dr[N],d[N],dis[N];//记录各点距离信息
int pre[N],a[N],vis[N],tot,maxn,t,pl,pr,l,r;//记录直径上的信息
bool flag;
void dfs(int x,int fa,int cnt) {
if(cnt==3) pre[x]=fa;//记录直径路径
for(int i=0; i<v[x].size(); i++) {
int y=v[x][i];
if(y==fa) continue;
d[y]=d[x]+1;
if(maxn<d[y]) maxn=d[y],t=y;
if(cnt==2) dl[y]=d[y];
if(cnt==3) dr[y]=d[y];
dfs(y,x,cnt);
}
}
void dfs2(int x,int fa) {
for(int i=0; i<v[x].size(); i++) {
int y=v[x][i];
if(y==fa || vis[y]==1) continue;
dfs2(y,x);
dis[x]=max(dis[x],dis[y]+1);
}
}
int main() {
cin>>n;
for(int i=1; i<n; i++) {
int x,y,z;
cin>>x>>y>>z;
v[x].push_back(y);
v[y].push_back(x);
c[i+1]=z;
}
t=1;
for(int i=1; i<=3; i++) {//进行3次dfs
maxn=0;
memset(d,0,sizeof d);
dfs(t,0,i);
if(i==1) pl=t;//获取直径的左端点
if(i==2) pr=t;//获取直径的右端点
}
for(int i=t; i; i=pre[i]) {
vis[i]=1;
a[++tot]=i;//从左到右标记直径上的点
}
for(int i=2; i<tot; i++) dfs2(a[i],0);//获取点x能到的不在直径上的最远点
l=a[1],r=a[tot];//使得右端点r靠左，左端点l靠右
for(int i=2; i<tot; i++) {
int x=a[i];
if(dis[x]==dr[x] && flag==false){
r=x;
flag=true;
}
if(dis[x]==dl[x]) l=x;
}
if(l==a[1]&&r==a[tot]) {//没有公共点
cout<<0;
return 0;
}
int ans=c[r];
while(l!=r) ans+=c[l],l=pre[l];
cout<<ans;
return 0;
}8.去掉再加上：
性质4分析：
uv连接后有两种情况1.新直径不过uv，即现直径为st或为xy。2.新直径过uv，则现直径为max(vs,vt)+max(ux,uy)+uv。这两种情况都能保证新直径端点为x,y,s,t中的任意两个。新直径为以上三个中最大值。
连边uv求新树直径最小：
引理性质4可知：
st与xy不变，此时只能减下过uv的直径大小。以max(vs,vt)为例，要使该值最小，则v应当在树的中心位置，这样vs与vt越均衡。同理u也应该在T2的树的中心位置。
连边uv求新树直径最大：与前面一致，以max(vs,vt)为例，要使得该值最大，则v应当选择直径端点位置。因此uv选择各自直径的端点位置时，直径最大。
9.例题：
题目描述：
给定一棵 n (1<=n<=1e4)个点构成的树。树中每条边的长度均为 1。现在，需要你去掉树中的一条边，然后再给树加上一条边，使得图形仍是树。请计算，新树的直径的最小可能值。(新树可以和原来的树完全一样)。
题目分析：
由性质4，我们知道连接时需要连接两棵树的中心，才能使得新树直径尽可能小。所以连接点很好处理。对于断开点，我们必然只有断开直径上的边，否则直径不可能变小，具体直径上哪一条边，我们可以进行枚举。
真确代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1E4+5;
vector<int>v[N];
int n,ans,maxn,t,pre[N],d[N];
bool vis[N][N];
void dfs(int x,int fa,int cnt,int k) {
if(cnt==2&&k==0) pre[x]=fa;
for(int i=0; i<v[x].size(); i++) {
int y=v[x][i];
if(y==fa||vis[x][y]) continue;
d[y]=d[x]+1;
if(d[y]>=maxn) maxn=d[y],t=y;
dfs(y,x,cnt,k);
}
}
int get(int x,int k) {
t=x;
for(int i=1; i<=2; i++) {
maxn=0;
memset(d,0,sizeof d);
dfs(t,0,i,k);
}
return maxn;
}
int main() {
cin>>n;
for(int i=1; i<n; i++) {
int x,y;cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
ans=get(1,0);
int ans=maxn,res;
for(int i=t; i; i=pre[i]) {
if(i==0||pre[i]==0) continue;
vis[i][pre[i]]=vis[pre[i]][i]=1;
int lena=get(i,1),lenb=get(pre[i],1);
res=max(max(lena,lenb),(lena+1)/2+(lenb+1)/2+1);
ans=min(ans,res);
res=0;
vis[i][pre[i]]=vis[pre[i]][i]=0;
}
cout<<ans;
return 0;
}树形结构（1 基础）：https://blog.csdn.net/Archie28/article/details/140532542
树形结构（3 树的中心、重心）：https://blog.csdn.net/Archie28/article/details/140532797
树形结构（总）：https://blog.csdn.net/Archie28/article/details/140504428
本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » C++树形结构（2 树的直径）
发表评论 取消回复