做公司 网站,加工订单网,好看的网页配色,网站备案为什么这么慢目录
一.树的中心#xff1a;
1.树的概念#xff1a;
2.树的性质#xff1a;
性质1#xff1a;
性质2#xff1a;
3.树的中心求解#xff1a;
4.例题#xff1a;
二.树的重心#xff1a;
1.基础概念#xff1a;
2.求解方法#xff1a;
3.例题#xff1a;…目录
一.树的中心
1.树的概念
2.树的性质
性质1
性质2
3.树的中心求解
4.例题
二.树的重心
1.基础概念
2.求解方法
3.例题
4.重心的性质
性质1
性质2
性质3
性质4
性质5
5.例题
①子树的重心
②唯一的重心
③会议 一.树的中心
除了直径的端点还有一个点我们完成题目时经常会用到这就是树的中心。
1.树的概念
以树的中心为根时从该根到每个叶子节点的最长路径最短使得路径和平衡。实际应用在若干村庄中树形结构修一个小学使得所有村庄到学校的最大距离最小小学应该修在什么位置
2.树的性质
性质1
树的中心一定在直径上且趋向于中点位置
性质2
树的中心可以有一个(单中心)也可以有两个(双中心)
证明引理性质2若树的中心p不在直径st上st上有一点q与直径联通。中心点能到的最远距离为max(qs,qt)pq若要使得该值最小pq应当为0因此p在直径上。同时为了让max(qs,qt)更小树的中心要在直径中点处。
3.树的中心求解
我们现在已经知道求解任意一点到两端点的距离即根据性质2可很轻松得到每个点能到的最长路径。求出每个点后的路径后一次遍历便可知树的中心点。
4.例题
题目描述
给定一棵树树中包含 n个结点编号1~n和 n−1 条无向边每条边都有一个正权值。请你在树中找到一个点使得该点到树中其他结点的最远距离最近。输出该节点以及最近距离。(若存在多个点的距离相同则输出编号较小的一个)
题目分析
有data数组表述每个点出发的最大距离因此我们在第2次和第3次dfs的过程中与dis数组比较即可。并且在第3次dfs时把最小距离求出来。
正确代码
#includebits/stdc.h
using namespace std;
int n,data[100001],dl[100001],maxn,maxn2,minn2e9,tmp,pl;
vectorint v[10001];
vectorint w[10001];
void dfs(int x,int fa,int cnt) {for(int i0; iv[x].size(); i) {int yv[x][i];if(yfa) continue;data[y]data[x]w[x][i];if(maxndata[y]) ply,maxndata[y];if(cnt3) {maxn2max(data[y],dl[y]);if(maxn2minn) minnmaxn2,tmpy;}dfs(y,x,cnt);}
}
int main() {cinn;for(int i1; in-1; i) {int x,y,z;cinxyz;v[x].push_back(y);v[y].push_back(x);w[x].push_back(z);w[y].push_back(z);}dfs(1,0,1);maxn0;memset(data,0,sizeof data);dfs(pl,0,2);for(int i1; in; i) dl[i]data[i];memset(data,0,sizeof data);maxn0;dfs(pl,0,3);couttmp minn;return 0;
}
二.树的重心
1.基础概念
使得最大子树大小最小。那么这个点叫就被叫做树的重心
在线性的序列[1,n]中我们在考虑用分治思想处理问题时需对问题进行划分。在划分问题时若要更加均匀我们选择中点mid可以更加高效。这样得到[1,mid],[mid1,n]两个子序列因为子序列中元素的个数n/2(向上取整)这样可以把问题复杂度优化到O(logn) 2.求解方法
显然要求树的重心我们可以枚举出每个点为断点时所产生的最大子树大小。某断点求当前最大子树大小的方法对该点进行dfs找到以i为根节点的子树的大小记录到sz[i]中接着在该点的儿子中找si最大的一个。复杂度为O(n2)
3.例题
题目描述
给定一棵树树中包含 nn1e5个结点编号1~n和 n−1 条无向边找出树的重心若重心不止一个则输出编号较小的以及当前重心下的最大子树大小。
题目分析
这是一道关于重心的基础题仅需用重心的求解方法再用之前讲的求最大子树的方法就可以了。
正确代码
#includebits/stdc.h
using namespace std;
const int N1e65;
vectorint v[N];
int d[N],minnN,n;//d数组记录当前节点子树的大小
int res,id;//id记录重心minn为重心下最大子树的大小
void dfs(int x,int fa) {d[x]1;int res0;//开始找以x为根的最大子树for(int i0; iv[x].size(); i) {int yv[x][i];if(yfa) continue;dfs(y,x);d[x]d[y];resmax(d[y],res);//打擂台找几个子树中的最大值}resmax(res,n-d[x]);//除最大字数为剩下的子树if(minnres) minnres,idx;
}
int main() {cinn;for(int i1; in; i) {int x,y;cinxy;v[x].push_back(y);v[y].push_back(x);}dfs(n,0);coutid minn;return 0;
}
4.重心的性质
设mss(u)表示以u为重心的最大子树s0(u)表示以u为根的子树大小,su(v)表示以u为根的的子树v大小。
性质1
重心点的最大子树大小不大于整棵树大小的一半。
证明
设u为重心v为u的最大子树。可以得出s0[u]-su[v]su[v] 即 su[v]s0[u]/2在整颗树中存在s0[u]n所以su[v]n/2得证以某点为根最大子树大小不超过n/2的都是树的重心
常用推导
Ⅰ.以某点为根最大子树大小不超过n/2的一定是树的重心。
Ⅱ.以root为根的有根树中树的重心一定在其最大的一颗子树内。具体来讲假设y为root的最大子树的儿子那么重心一定在tp[y]-root的这一条链中tp[y]表示子树y的重心。
性质2
非空树有且仅有1-2个重心。当有两个重心时树定有偶数个节点且两个重心相邻。
证明
假设u、v为树上两个重心uv分别为对方最长链上的点。此时mss[u]mss[v]又设k为两个重心之间存在的点数。由mss[u]su[v]kmss[v]sv[u]k,推出sv[u]su[v]。在k个点中选择中点p此时mss[p]max(su[v]k/2,sv[u]k/2) su[v]k,当且仅当k0时不等式成立。重心u、v之间必不可能有点。所以若有两个重心则重心必然相邻。
性质3
树中所有点到重心的距离和最小反过来距离和最小的点一定是重心。
证明
当前重心为u。mss[u]su[v]。假设重心从u移动到vmss[v]sv[u]可得1类节点到重心的距离加12类节点到重心的距离减少1因此当增加部分sv[u] 小于 减少部分 sv[u]时距离和减少所以当su[v]sv[u]时重心移动得到mss更小。反之若当前mss已经最小则无法再产生一个更小距离和。
性质4
往树上增加或减少一个叶子如果原节点数是奇数那么重心可能增加一个原重心仍是重心如果原点数是偶数重心可能减少一个另一个重心仍是重心。节
性质5
把两棵树通过一条边相连得到一棵新的树则新的重心在较大的一棵树一侧的连接点与原重心之间的简单路径上。如果两棵树大小一样则重心就是两个连接点。
5.例题
①子树的重心
题目描述
输入一棵树,判断每一棵子树的重心是哪一个节点。第一行输入n,q。n表示树的节点个数q表示询问次数。第二行n-1个数分别表示从节点2开始各节点的父亲节点。后面q行每行一个数x表示询问当前以x为根的子树中树的重心位置。(n,q3e5)
题目分析
本题若对每一次询问都查询一遍子树的重心那么复杂度为O(nq)。在我们求一颗树T的重心时根据推导2知道重心一定在最大子树的重心到该树T的根这一条链上。所以我们如果知道最大子树的重心此时就可以遍历这一条链上的点根据推导1只要该点满足其最大子树大小不超过n/2那么一定是重心。所以我们可以dfs下去先求出小的子树重心回溯时再把当前的重心进行记录即可。复杂度O(nq)
正确代码
#includebits/stdc.h
using namespace std;
const int N1e65;
vectorint v[N];
int d[N],minnN,res,id[N],n,t[N],s[N],q;
void dfs(int x) {d[x]1;int res0;for(int i0; iv[x].size(); i) {int yv[x][i];dfs(y);d[x]d[y];if(d[y]d[id[x]]) id[x]y;//找子树最大的“儿子”}if(id[x]0) {//叶子节点的重心就是自己t[x]x;return;}t[x]t[id[x]];//从“儿子”的重心调到自身满足条件且靠近xwhile(d[t[x]]*2d[x]) t[x]s[t[x]];//向上找重心
}
int main() {cinnq;for(int i2; in; i) {int x;cinx;s[i]x;v[x].push_back(i);}dfs(1);//有根树往下进行dfsfor(int i1; iq; i) {int y;ciny;coutt[y]endl;}return 0;
}
//d[i]表示以i为根的子树大小
//s[i]表示节点i的父亲节点
//id[i]表示以i为根的有根树的最大子树
//t[i]表示以i为根的有根数的重心
②唯一的重心
题目描述
给定一棵节点数为 n(n3e5) 的树 删一条边然后加上一条边 使得该树的重心唯一 。删掉的边和加上的边可以是同一条输出删边与加边信息本题多测。
题目分析
若存在一个重心删边与加边都可以是同一条边。若不止一个重心引理性质2最多存在两个重心且重心直接相连。假设两重心分别为idxidy。要保证只留下一个重心那就应当对某个重心子树idx进行修改删除其叶子节点的一条边且将该叶子节点直接连到另一个重心idy上即可。
正确代码
#includebits/stdc.h
using namespace std;
const int N3e55;
int n,minnN,z1,z2;//z1、z2两个重心
int u,sz[N],f[N];//u是断开的叶子节点
vectorintv[N];
void dfs(int x,int fa) {sz[x]1,f[x]fa;int res0;for(int i0; iv[x].size(); i) {int yv[x][i];if(yfa) continue;sz[x]sz[y];resmax(res,sz[y]);}resmax(res,n-sz[x]);if(minnres) z1x,z20,minnres;else if(minnres) z2x;
}
void dfs1(int x,int fa) {if(v[x].size()1) ux;for(int i0; iv[x].size(); i) {int yv[x][i];if(yfa) continue;dfs1(y,x);}
}
int main() {int t;cint;while(t--) {cinn;for(int i1; in; i) {int x,y;cinxy;v[x].push_back(y);v[y].push_back(x);}dfs(1,0);if(z20) {//只有一个重心就直接输出cout1 v[1][0]endl1 v[1][0]endl;continue;}if(f[z1]!z2) swap(z1,z2);//保证只有一个重心在子树上遍历dfs1(z1,z2);coutu f[u]endlu z2endl;for(int i1; in; i) {f[i]0,v[i].clear();}minnN,z1z20;}return 0;
}
③会议
题目描述
有一个村庄居住着 n 个村民有 n−1 条路径使得这 n 个村民的家联通每条路径的长度都为 1。现在村长希望在某个村民家中召开一场会议村长希望所有村民到会议地点的距离之和最小那么村长应该要把会议地点设置在哪个村民的家中并且这个距离总和最小是多少若有多个节点都满足条件则选择节点编号最小的那个点。
题目分析
求所有点到某点的距离和根据重心性质3显然是到重心最小因此求出重心在进行距离和统计即可。
正确代码
#includebits/stdc.h
using namespace std;
const int N5e45;
int n,minnN,idx,idy,sum,u,sz[N];//sz数组记录当前节点的子树大小
vectorintv[N];
void dfs(int x,int fat) {sz[x]1;int res0;for(int i0; iv[x].size(); i) {int yv[x][i];if(yfat) continue;dfs(y,x);sz[x]sz[y];resmax(sz[y],res);}resmax(res,n-sz[x]);if(minnres) idxx,minnres;else if(minnresidxx) idxx;
}
void dfs1(int x,int fat,int num) {sumnum;for(int i0; iv[x].size(); i) {int yv[x][i];if(yfat) continue;dfs1(y,x,num1);}
}
int main() {cinn;for(int i1; in; i) {int x,y;cinxy;v[x].push_back(y);v[y].push_back(x);}dfs(1,0);//找重心dfs1(idx,0,0);//统计距离和coutidx sum;return 0;
}
树形结构1 基础https://blog.csdn.net/Archie28/article/details/140532542
树形结构2 树的直径https://blog.csdn.net/Archie28/article/details/140532713
树形结构总https://blog.csdn.net/Archie28/article/details/140504428
