树的直径是指树上距离最远的2个点的距离,由于本蒟蒻之前不知道这用操作而吃过亏,故在此缅怀一下。

整理一些树的,基本的,简单的一些知识。

  树的直径有2种求法,搜索或dp。

先写一下关于树的定义,相关术语。

  搜索的话最好用bfs,可以o(n)的搜,dfs或许会爆栈。随便从一个点往外搜,找到距离最远的点,在从这个点搜距离最远的点,这两点的路径即树的直径。

树,父节点、子节点、子树、祖先、兄弟、根节点、叶节点、直径、路径、重心、直径、最近公共祖先、生成树、dfs序,树形dp等

  dp的话,从一个点找所有点与他的距离,最远的与次远的2个点组成的即为树的直径。

 

1、最近公共祖先

一般用倍增求LCA(Least
Common Ancestors)。

按照朴素的做法,就是深的点跳到同一高度,然后两个点一齐往上跳。跳到同一位置。

这样其实不慢,一般的树,深度为logn,所以这个复杂度可以是logn。但如果树成了一条链,那么复杂度就是O(n)。

而倍增求LCA,和这个思想是一样的,深的点跳到同一高度,然后两个点一齐往上跳。不过它不是一个点一个点的跳,看下面。

对于任何的数字都可以分解成2的次幂相加的形式(7
= 22+21+20,10 =
23+21…),证明也很简单,任何一个十进制都可以分解成二进制表示。

那么对于跳的任何高度都可以用二进制表示(跳7个,7
= 22+21+20,跳10个10 =
23+21),那么我们预处理出每个点往上跳2的次幂的点,所到达的点是谁就好了。

然后和上面一样跳。

这样明显比上面的快。

贴一下代码
luogu3379

 

图片 1图片 2

 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\n",lca(a,b));
77     }
78     return 0;
79 }

View Code

 

2、生成树

生成树计数

 

最小/大生成树

prime算法和kruskal
算法。一般用kruskal 吧。

kruskal
算法原理很简单,以最小生成树为例。求最大的权值尽量小和且构成一棵树。

先按每条边的权值大小排序,从小到大依次加入,并查集判断是否成为连通图了即可

代码

图片 3图片 4

 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 }

View Code

 

3、树的直径

两次bfs(dfs),指定任意一点为根,搜索出距离这个根最远的点a,然后搜距离a最远的点b,ab之间的路径为为树的直径。

代码
原题(poj2631 Roads in the North)

图片 5图片 6

 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 }

View Code

 

4、树的重心

树的重心定义:树中的一个点,删掉这个点,使得剩下的树所构成的森林中最大的子树节点数最少。

树的重心推论:

1.设树上的一个点S,树上其余所有点到S点的距离之和最小,那么S就是重心。

2.树的重心不唯一。

然后可以依靠定义来求树的重心。

首先以任意一个点,进行dfs,dfs过程中统计以每个点为根的子树中,一共含有多少节点。

然后
总节点数 减去 子树的节点数 减去1(自己),就是它父亲那边点的数量。

做差之后取最小值。

代码:poj3107

图片 7图片 8

 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("\n");    
59     }    
60     return 0;
61 }

View Code

 

5、dfs序

关于这个的内容太多了。这里之简要的叙述一下好了。

dfs序就是按照dfs的顺序所构成的一个序列,(从名字解释的qwq)

dfs的性质:一棵子树所在的位置处于一个连续区间中。

deth[x]为x的深度,L[x]为dfs序中x的起始位置,R[x]为dfs序中x子树的结束位置

然后处理子树上的问题成立处理区间的问题,在树上也变成了在序列上,所以可以用线段树或者树状数组维护了。

求dfs序的代码

图片 9图片 10

 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 }

View Code

 

 

 

总结

这是一篇入门基础级的,没有更多的叙述。(以后再加以补充吧)

树的问题还有很多,这些都是关于基础的一些问题,更多的,感兴趣可以深入的研究;

谢谢观看

 

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注