关键词：
整理一些树的，基本的，简单的一些知识。
先写一下关于树的定义，相关术语。
树，父节点、子节点、子树、祖先、兄弟、根节点、叶节点、直径、路径、重心、直径、最近公共祖先、生成树、dfs序，树形dp等
1、最近公共祖先
一般用倍增求LCA（Least Common Ancestors）。
按照朴素的做法，就是深的点跳到同一高度，然后两个点一齐往上跳。跳到同一位置。
这样其实不慢，一般的树，深度为logn，所以这个复杂度可以是logn。但如果树成了一条链，那么复杂度就是O(n)。
而倍增求LCA，和这个思想是一样的，深的点跳到同一高度，然后两个点一齐往上跳。不过它不是一个点一个点的跳，看下面。
对于任何的数字都可以分解成2的次幂相加的形式（7 = 2^2+2^1+2^0,10 = 2^3+2^1...），证明也很简单，任何一个十进制都可以分解成二进制表示。
那么对于跳的任何高度都可以用二进制表示（跳7个,7 = 2^2+2^1+2^0，跳10个10 = 2^3+2^1），那么我们预处理出每个点往上跳2的次幂的点，所到达的点是谁就好了。
然后和上面一样跳。
这样明显比上面的快。
贴一下代码 luogu3379
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 5 using namespace std; 6 const int N = 1000100; 7 8 struct Edge { 9 int v,nxt; 10 } e[N]; 11 int f[N][25]; 12 int deth[N]; 13 int head[N]; 14 int n,m,s,tot,a,b,d; 15 16 void add(int u,int v) { 17 tot++; 18 e[tot].v = v; 19 e[tot].nxt = head[u]; 20 head[u] = tot; 21 } 22 23 void dfs(int x) { 24 for (int i=head[x]; i; i=e[i].nxt) { 25 int v = e[i].v; 26 if(!deth[v]) 27 { 28 deth[v] = deth[x]+1; 29 f[v][0] = x; 30 dfs(v); 31 } 32 } 33 } 34 35 void init() { 36 for (int j=1; j<=20; ++j) 37 for (int i=1; i<=n; ++i) 38 f[i][j] = f[f[i][j-1]][j-1]; 39 } 40 41 int lca(int u,int v) { 42 if (deth[u] < deth[v]) swap(u,v); 43 /*for (int i=20; i>=0; --i) 44 { 45 if (deth[f[u][i]] >= deth[v]) 46 u = f[u][i]; 47 }*/ 48 d = deth[u]-deth[v]; 49 for (int i=0; i<=20; ++i) { 50 if ((1<<i) & d) 51 u = f[u][i]; 52 } 53 if (u==v) return u; 54 for (int i=20; i>=0; --i) { 55 if(f[u][i] != f[v][i]) { 56 u = f[u][i]; 57 v = f[v][i]; 58 } 59 } 60 return f[u][0]; 61 } 62 63 int main() { 64 scanf("%d%d%d",&n,&m,&s); 65 for (int i=1; i<n; ++i) { 66 scanf("%d%d",&a,&b); 67 add(a,b); 68 add(b,a); 69 } 70 deth[s] = 1; 71 f[s][0] = 0; 72 dfs(s); 73 init(); 74 for (int i=1; i<=m; ++i) { 75 scanf("%d%d",&a,&b); 76 printf("%d ",lca(a,b)); 77 } 78 return 0; 79 }
2、生成树
生成树计数
最小/大生成树
prime算法和kruskal 算法。一般用kruskal 吧。
kruskal 算法原理很简单，以最小生成树为例。求最大的权值尽量小和且构成一棵树。
先按每条边的权值大小排序，从小到大依次加入，并查集判断是否成为连通图了即可
代码
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 const int MAXM = 200100; 8 const int MAXN = 100100; 9 10 struct edge { 11 int a,b,c; 12 } e[MAXM]; 13 int fa[MAXN]; 14 15 int find(int a) { 16 return fa[a]==a?a:fa[a]=find(fa[a]); 17 } 18 bool cmp(edge a,edge b) { 19 return a.c<b.c; 20 } 21 int main() { 22 int n,m,ans,cnt; 23 scanf("%d%d",&n,&m); 24 for(int i=1; i<=n; ++i) fa[i] = i; 25 for(int i=1; i<=m; ++i) { 26 int a,b,c; 27 scanf("%d%d%d",&a,&b,&c); 28 e[i].a=a; 29 e[i].b=b; 30 e[i].c=c; 31 } 32 sort(e+1,e+m+1,cmp); 33 for(int i=1; i<=m; ++i) { 34 int aa = find(e[i].a); 35 int bb = find(e[i].b); 36 if(aa!=bb) { 37 cnt++; 38 fa[aa] = bb; 39 ans += e[i].c; 40 if(cnt==(n-1))break; 41 } 42 } 43 if(cnt==(n-1)) cout<<ans; 44 else cout<<"-1"; 45 return 0; 46 }
3、树的直径
两次bfs(dfs)，指定任意一点为根，搜索出距离这个根最远的点a，然后搜距离a最远的点b，ab之间的路径为为树的直径。
代码 原题（poj2631 Roads in the North）
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 #include<cstring> 5 6 using namespace std; 7 8 const int MAXN = 10010; 9 10 struct Edge{ 11 int to,w,nxt; 12 Edge(){} 13 Edge(int x,int y,int z){to = x,w = y,nxt = z;} 14 }e[500100]; 15 16 int head[MAXN<<1],dis[MAXN]; 17 int tot; 18 queue<int>q; 19 20 int bfs(int x) 21 { 22 memset(dis,-1,sizeof(dis)); 23 q.push(x); 24 dis[x] = 0; 25 int id,mx = 0; 26 27 while (!q.empty()) 28 { 29 int u = q.front(); 30 q.pop(); 31 for (int i=head[u]; i; i=e[i].nxt) 32 { 33 int v = e[i].to, w = e[i].w; 34 if (dis[v]==-1) //双向边，只算一次 35 { 36 dis[v] = dis[u]+w; 37 if (dis[v]>mx) mx = dis[v],id = v; 38 q.push(v); 39 } 40 } 41 } 42 return id; 43 } 44 int main() 45 { 46 int u,v,w; 47 while (scanf("%d%d%d",&u,&v,&w)!=EOF) 48 { 49 e[++tot] = Edge(v,w,head[u]); 50 head[u] = tot; 51 e[++tot] = Edge(u,w,head[v]); 52 head[v] = tot; 53 } 54 printf("%d",dis[bfs(bfs(1))]); 55 return 0; 56 }
4、树的重心
树的重心定义：树中的一个点,删掉这个点，使得剩下的树所构成的森林中最大的子树节点数最少。
树的重心推论：
1.设树上的一个点S，树上其余所有点到S点的距离之和最小，那么S就是重心。
2.树的重心不唯一。
然后可以依靠定义来求树的重心。
首先以任意一个点，进行dfs，dfs过程中统计以每个点为根的子树中，一共含有多少节点。
然后 总节点数 减去 子树的节点数 减去1(自己)，就是它父亲那边点的数量。
做差之后取最小值。
代码：poj3107
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 5 using namespace std; 6 7 const int MAXN = 50010; 8 const int MAXM = 100010; 9 10 struct Edge{ 11 int to,nxt; 12 }e[MAXM]; 13 int head[MAXM],tot; 14 int son[MAXN]; 15 int ans[MAXN],p,Ans = 1e9,n; 16 17 inline int read() { 18 int x = 0,f = 1;char ch = getchar(); 19 for (; ch<‘0‘||ch>‘9‘; ch = getchar()) 20 if (ch==‘-‘) f = -1; 21 for (; ch>=‘0‘&&ch<=‘9‘; ch = getchar()) 22 x = x*10+ch-‘0‘; 23 return x*f; 24 } 25 inline void init() { 26 memset(head,0,sizeof(head)); 27 memset(son,0,sizeof(son)); 28 tot = 0; 29 } 30 inline void add_edge(int u,int v) { 31 e[++tot].to = v,e[tot].nxt = head[u],head[u] = tot; 32 } 33 void dfs(int u,int fa) { 34 int cnt = 0; 35 for (int i=head[u]; i; i=e[i].nxt) { 36 int v = e[i].to; 37 if (v==fa) continue; 38 dfs(v,u); 39 son[u] += son[v]+1; 40 cnt = max(cnt,son[v]+1); 41 } 42 cnt = max(cnt,n-son[u]-1); 43 if (cnt<Ans) {Ans = cnt,p = 0,ans[++p] = u;} 44 else if (cnt==Ans) {ans[++p] = u;} 45 } 46 int main() { 47 48 while (scanf("%d",&n)!=EOF) { 49 init(); 50 for (int u,v,i=1; i<n; ++i) { 51 u = read(),v = read(); 52 add_edge(u,v),add_edge(v,u); 53 } 54 dfs(1,0); 55 sort(ans+1,ans+p+1); 56 for (int i=1; i<=p; ++i) 57 printf("%d ",ans[i]); 58 printf(" "); 59 } 60 return 0; 61 }
5、dfs序
关于这个的内容太多了。这里之简要的叙述一下好了。
dfs序就是按照dfs的顺序所构成的一个序列，（从名字解释的qwq）
dfs的性质：一棵子树所在的位置处于一个连续区间中。
deth[x]为x的深度，L[x]为dfs序中x的起始位置，R[x]为dfs序中x子树的结束位置
然后处理子树上的问题成立处理区间的问题，在树上也变成了在序列上，所以可以用线段树或者树状数组维护了。
求dfs序的代码
1 void dfs(int u,int fa) { 2 deth[u] = deth[fa]+1; 3 q[++tot] = u; 4 L[u] = tot; 5 for (int i=head[u]; i; i=e[i].nxt) { 6 int v = e[i].to; 7 if (v==fa) continue; 8 dfs(v,u); 9 } 10 R[u] = tot; 11 }
总结
这是一篇入门基础级的，没有更多的叙述。（以后再加以补充吧）
树的问题还有很多，这些都是关于基础的一些问题，更多的，感兴趣可以深入的研究；
谢谢观看
关于融合模型的一些简单整理（stackingblending）
目前，模型融合的方式有很多，比较常用的包括Voting法、Stacking法以及Blending法。一、VotingVoting是模型融合策略中最简单的一种方法，其融合过程不需要建立新的模型，只需要在单一模型的输出结果上完成融合。Vot... 查看详情
关于最小生成树的prim算法和kruskal算法
针对一些城市之间建造公路或者造桥问题，我们需要的是以最小代价完成任务，看了一下别人的代码，思想其实都是差不多，但是感觉不大好理解，比如Kruskal算法中有人写了利用递归实现判断是否形成环，本人愚钝，没有想通... 查看详情
关于线段树的一些学习笔记——（无限施工中）
（施工中orz） 20171223：更新一些关于线段树的基础用法，以及简单的zkw线段树、权值线段树，动态开点线段树，线段树的标记永久化，主席树，可持久化线段树，可持久化线段树的标记永久化（施工中） 这几天学了... 查看详情
golang关于interface的学习整理
Golang－interface（四反射）go语言学习-reflect反射理解和简单使用为什么在Go语言中要慎用interfacegolang将interface转换为structgoreflectstruct遍历,反射GolangReflect反射的使用详解1Go语言反射三定律 查看详情
python圣诞树编写实例详解(代码片段)
...用Turtle绘制复杂圣诞树在本篇文章里小编给大家整理的是关于python圣诞树代码的相关内容，有兴趣的朋友们可以学习下。python圣诞树代码1、简单的绘制圣诞树新建tree1.py或者直接输入下面代码运行#声明树的高度height=5#树... 查看详情
关于微服务整理
微服务架构的优点：每个服务都比较简单，只关注于一个业务功能。微服务架构方式是松耦合的，可以提供更高的灵活性。微服务可通过最佳及最合适的不同的编程语言与工具进行开发，能够做到有的放矢地解决针对性问题。每... 查看详情
关于接口测试调试的一些总结整理
1.当请求接口返回值为404时，可以查看请求ip,port,address是否正确2.当请求接口返回值为406时，可以查看请求头是否设置了Accept，可以设置成:application/json,text/plain,/3.不同的接口可能使用的提交方式不一样，这时候信息头中的Content-T... 查看详情
关于如何修改电脑虚拟内存的整理
电脑的虚拟内存不够用时，我们经常会到处找处理的方法，其实方法很简单我想说的是:百度大法好，百度大法不行再谷歌下面贴出windows7的解决办法百度知道地址:https://jingyan.baidu.com/article/a17d5285ebbcea8099c8f266.html通过上面的方法... 查看详情
关于机器学习中决策树的相关问题也谈随机森林
前言 决策树可能是对于相关样本进行分类示性最为直观的一种方法，使用决策树方法来演示分类的过程对于读者而言可能也是最简单的一种方式，我们可以称之为它是白箱算法，所谓白箱就是直接可以对其进行观察... 查看详情
cogs2039.树的统计
...对比时间限制：1s 内存限制：128MB【题目描述】关于树的统计问题有多种多样的版本，这里你需要解决一个比较简单的问题：对于一棵包含N个节点的有根树，将所有点从1到N编号后，对于每一个节点v，统计出以v为根的子... 查看详情
cogs2039树的统计x
...对比时间限制：1s 内存限制：128MB【题目描述】关于树的统计问题有多种多样的版本，这里你需要解决一个比较简单的问题：对于一棵包含N个节点的有根树，将所有点从1到N编号后，对于每一个节点v，统计出 查看详情
poj3468整理一下线段树的写法
//对于延迟更新，我们在updata和query的时候pushdown和pushup两个东西都要存在#include<iostream>#include<cstdio>#include<cstring>#include<queue>usingnamespacestd;typedeflonglongll;structnode{lll,r,sum,add 查看详情
cogs2039.树的统计
...对比时间限制：1s 内存限制：128MB【题目描述】关于树的统计问题有多种多样的版本，这里你需要解决一个比较简单的问题：对于一棵包含N个节点的有根树，将所有点从1到N编号后，对于每一个节点v，统计出以v为根的子... 查看详情
树链剖分整理(代码片段)
...值，那么问题就不简单了。很容易发现这有些类似于线段树的问题，但 查看详情
周记2(代码片段)
...了二叉树和分支数目无限制的有根树的存储结构，而没有关于二叉树的遍历过程。为此对二叉树做个简单的总结，介绍一下二叉树基本概念、性质、二叉树的存储结构和遍历过程，主要包括先根遍历、中根遍历、后根遍历和层次... 查看详情
完全二叉树编号关于位运算的规律题——222.完全二叉树的节点个数(代码片段)
文章目录题目解题分析解题代码题目OJ平台解题分析如果仅仅不去利用性质做题的话，很简单！具体实现没啥好说的。intcountNodes(structTreeNode*root)if(!root)return0;returncountNodes(root->left)+countNodes(root->right)+1;利用完全二... 查看详情
数据结构学习笔记（二叉树）总结与整理(代码片段)
...09;总结与整理二叉树定义二叉树结构二叉树常用操作二叉树的创建递归方式二叉树的遍历非递归方式二叉树的遍历二叉树的其他功能堆（二叉树的顺序结构）堆的实现二叉树定义概念：一棵二叉树是结点的一个有限集... 查看详情
数据结构学习笔记（二叉树）总结与整理(代码片段)
...09;总结与整理二叉树定义二叉树结构二叉树常用操作二叉树的创建递归方式二叉树的遍历非递归方式二叉树的遍历二叉树的其他功能堆（二叉树的顺序结构）堆的实现二叉树定义概念：一棵二叉树是结点的一个有限集... 查看详情