植树节已过，小小的来点树

收藏[2044]PID[78452508]_标题[2019！]画师[Kros]UID[6350593]

树的重心

树的重心是什么？

对于一棵无根树，设其中的一个节点作为根，则可以形成一棵有根树。

该树以根为分界，分为若干个子树，设其中最大子树具有的节点数为 x 。

所有节点里， x 值最小的节点就是该树的重心，也叫质心。

与其相似的解释：

如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树节点数并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的重心。

（这里以及下文中的「子树」若无特殊说明都是指无根树的子树，即包括「向上」的那棵子树，并且不包括整棵树自身。）

重心的性质

重心相当于树的平衡点，其尽量均匀地将树分割成了若干部分。

在树分治以及树同构中，重心都具有相当重要的地位。

重心具有几个比较重要的性质：

①一棵树最少有一个重心，最多有两个重心，若有两个重心，则他们相邻（即连有直接边）。

②树上所有点到某个点的距离和里，到重心的距离和最小；若有两个重心，则其距离和相同。

③若以重心为根，则所有子树的大小都不超过整棵树的一半。否则可以通过平移使得最大子树的大小缩小至整树的一半，剩下子树的大小最大为 n/2−1 。此时新平移到的点才是真正的重心。

④在一棵树上添加或删除一个叶子节点，其重心最多平移一条边的距离。

⑤两棵树通过连一条边组合成新树，则新树重心在原来两棵树的重心的连线上。

如何求解重心？

按其定义来求即可。

我们任选一个节点作为根，然后跑DFS，在过程中记录每个节点各个子树的大小。对于每个节点，其还存在一个上方的子树（即从假设根到当前节点），其大小为总节点数减去当前节点的总子树大小。

然后就能得到每个节点最大子树的节点数，取其中最小值即可。

整个算法只需要遍历一遍树，时间复杂度为 O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int siz[N],wgt[N];
//wgt存储最大子树
//siz存储子树的节点数
int n,mi=INF,ans;//mi=min max size, ans=重心
void dfs(int now,int fa)
{
    siz[now]=1;
    wgt[now]=0;
    for(int i=0;i<e[now].size();i++)
    {
        int to=e[now][i];
        //遍历
        if(to==fa) continue;
        //是父亲节点就跳过
        dfs(to,now);
        //往下搜索
        siz[now]+=siz[to];
        //加起来
        wgt[now]=max(wgt[now],siz[to]);
        //取最大
    }
    wgt[now]=max(wgt[now],n-siz[now]);
    //注意每棵树还要上面的一颗子树，为总结点数减去当前节点的总子树大小
    if(wgt[now]<mi) mi=wgt[now],ans=now;
    //记录答案和节点
}

树的直径

基本概念

简单路径：路径上的所有点至多只访问了一次。

树的直径：树上最长的简单路径。

简单来说，定义一棵树 T=(V,E)，其直径为 maxlen(u,v)(u,v∈V)。

树的直径有两种常用求法，分别是两次DFS以及树形DP。

两次DFS求直径

算法思想

①从任意一点P出发，通过DFS寻找离它最远的点Q。

②再次从点Q出发，通过DFS寻找离它最远的W。

③直径即为WQ。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
using namespace std;
vector<int>edge[100005];
int vis[100005];
int dis[100005];
void dfs(int st)
{
    for(int i=0;i<edge[st].size();i++)
    {
        int to=edge[st][i];
        if(!vis[to])
        {
            vis[to]=1;
            dis[to]=dis[st]+1;//注意，本代码计算的是无权树的直径，所以边权为1
            //如果是有权树，则这里的1要改为边权
            dfs(to);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;//n个点
    for(int i=1;i<=n-1;i++)//因为是树，有n-1条边
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);
        edge[v].push_back(u);//无向图存储，若是有权树还要用结构体
    }
    dfs(1);//从1出发dfs一边
    int maxlen=0,Q,W,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(dis[i]>maxlen) 
            maxlen=dis[i],Q=i;
        dis[i]=vis[i]=0;
    }//找到直径的一个端点Q
    dfs(Q);//从Q出发
    for(int i=1;i<=n;i++)
        if(dis[i]>ans) ans=dis[i],W=i;//找到另一个端点W，同时得到直径长度
    return 0;
}

树形DP

树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。

平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：

  1. 叶－>根：在回溯的时候从叶子节点往上更新信息
  2. 根 - >叶：往往是在从叶往根dfs一遍之后（相当于预处理），再重新往下获取最后的答案。

不管是 从叶－>根 还是 从 根 - >叶，两者都是根据需要采用，没有好坏高低之分。

以一道经典例题开始叙述罢

没有上司的舞会

题目描述

某大学有 \(n\) 个职员，编号为 \(1\ldots n\)。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 \(n\)。

第 \(2\) 到第 \((n + 1)\) 行，每行一个整数，第 \((i+1)\) 行的整数表示 \(i\) 号职员的快乐指数 \(r_i\)。

第 \((n + 2)\) 到第 \(2n\) 行，每行输入一对整数 \(l, k\)，代表 \(k\) 是 \(l\) 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

样例输出 #1

1
5

提示

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1\leq n \leq 6 \times 10^3\)，\(-128 \leq r_i\leq 127\)，\(1 \leq l, k \leq n\)，且给出的关系一定是一棵树。

1
2
3
4
5
6
7
8
9
10
11
 经典的树形dp

设f[x][0]表示以x为根的子树,且x不参加舞会的最大快乐值

f[x][1]表示以x为根的子树，且x参加了舞会的最大快乐值

则f[x][0]={max(f[y][0],f[y][1])} (y是x的儿子)

f[x][1]={f[y][0]}+h[x] (y是x的儿子)

先找到唯一的树根root 则ans=max(f[root][0],f[root][1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
//没有上司的舞会
//定义f[u][0]为u节点没有被选，u所在子树的最大权值和
//f[u][1]表示u被选时候的子树最大权值和
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
const int N=6005;
vector<int>G[N];
int n;
int a[N];
int f[N][2];
void dfs(int u,int fa)
{
	f[u][0]=0;
	f[u][1]=a[u];
	for(auto v:G[u])
	{
		if(v!=fa)
		{
			dfs(v,u);
            //本题属于先遍历到叶子节点后往上推
			f[u][0]+=max(f[v][0],f[v][1]);
            //上司不去，下属可以去可以不去
			f[u][1]+=f[v][0];
            //上司去了，那么下属不去
		}
	}	
}
int main()
{
	cin>>n;
	rep(i,1,n){
		cin>>a[i];
	}
	rep(i,1,n-1)
	{
        //建树
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1,0);
	cout<<max(f[1][0],f[1][1]);
    //取最大
}