概念应用例题最大独立子集 没有上司的晚会题目描述分析 树的重心题目描述分析 树的直径概念题目描述分析

概念

给定一棵有N个节点的树(通常是无根树，也就是有N-1条无向边)，我们可以任选一个节点为根节点，从而定义出每个节点的深度和每棵子树的根。 在树上设计动态规划算法时，一般就以节点从深到浅(子树从小到大)的顺序作为DP的“阶段”。DP的状态表示中，第一维通常是节点编号(代表以该节点为根的子树)。大多数时候，我们采用递归的方式实现树形动态规划。对于每个节点x，先递归在它的每个子节点上进行DP，在回溯时，从子节点向节点x进行状态转移。

简单点说，其实，就是dfs，但这个dfs，时间复杂度要小的很多，并且，具体操作使用数组来模拟不同情况 并且，很多时候，线性dp的可以演变成树形DP，如背包

应用

1.最大独立子集 2.树的重心 3.树的直径

例题

最大独立子集 没有上司的晚会

题目描述

Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。 输入格式 第一行一个整数N。(1≤N≤6000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。 最后一行输入0,0。 输出格式 第1行：输出最大的快乐指数。 样例 样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 样例输出 5

分析

首先拿到这个题，就会先把根给求出来 然后，分析题意，其实，如果选fa，那，son一定不行，但不选fa，son可选可不选，这时，我们就会想到，打dfs,或dp，但又想想，dfsO(2^n),肯定不好，dp，虽然好像可以，但，好像没有阶段，于是，就要用树形DP dp[x][0] =max(dp[s][0],dp[s][1]) dp[x][1] = H[x] + dp[son][0](son∈Son(x) 比如dp[i][1]表示以i号节点为子树的根，当它参会时整棵子树的快乐指数和；dp[i][0]表示以i号节点为子树的根，当它不参会时整棵子树的快乐指数和 很明显，这就是由叶节点，一点点的传到根

#include<bits/stdc++.h> using namespace std; int n; int a[100050]; int x,y; vector<int>g[100005]; int dp[10005][2]; int fa[100005]; int root; void dfs(int x) { dp[x][1]=a[x]; dp[x][0]=0; for(int i=0;i<g[x].size();i++) { int v=g[x][i]; dfs(v); dp[x][1]+=dp[v][0]; dp[x][0]+=max(dp[v][0],dp[v][1]); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n-1;i++) { scanf("%d %d",&x,&y); g[y].push_back(x); fa[x]=1; } for(int i=1;i<=n;i++) { if(!fa[i]) { root=i; break; } } dfs(root); printf("%d",max(dp[root][1],dp[root][0])); }

树的重心

首先，我们要知道，什么是重心 树的重心定义为，当把节点x去掉后，其最大子树的节点个数最少(或者说成最大连通块的节点数最少)，那么节点x就是树的重心。 他有以下几个性质 1、删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心，且相邻； 2、树中所有节点到重心的距离之和最小，如果有两个重心，那么它们距离之和相等； 3、两个树通过一条边合并，新的重心在原树两个重心的路径上； 4、树删除或添加一个叶子节点，重心最多只移动一条边。 还有，一棵树，重心最多2个，n%2= =0有2个，n%2= =1有一个 运用第一个性质，可以解决大多数问题

题目描述

树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后，树将分成两个连通块：（2,4,5），（3,6,7），则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，（4），（5），（1,3,6,7）最大的连通块包含4个节点；第一种方法可以得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。 输入格式 输入：第一行一个整数n，表示树的结点个数。（n<100） 接下来n-1行，每行两个数i，j。表示i和j有边相连。 输出格式 输出：第一行一个整数k，表示重心的个数。 接下来K行，每行一个整数，表示重心。按从小到大的顺序给出。 样例 样例输入 7 1 2 1 3 2 4 2 5 3 6 3 7 样例输出 1 1

分析

运用第一个性质，我们可以排除那些不是重心的，然后，输出剩下的 可以统计任选一个节点为根，把无根树变成有根树，然后dp[i]表示以i为根的子树的节点个数 dp[i]=∑dp[son]+1 这只是部分子树，还有当前节点的长辈，节点总数为n-dp[now]，然后在做比较

#include<bits/stdc++.h> using namespace std; int n; int x,y; int dp[100054]; vector<int>g[10005]; vector<int>ans; int vis[10005]; void dfs(int x) { bool flag=1; dp[x]=1; for(int i=0;i<g[x].size();i++) { int v=g[x][i]; if(vis[v]) { continue; } vis[v]=1; dfs(v); dp[x]+=dp[v]; if(dp[v]>n/2) { flag=0; } } if(n-dp[x]>n/2) { flag=0; } if(flag) { ans.push_back(x); } } int main() { scanf("%d",&n); for(int i=1;i<n;i++) { scanf("%d %d",&x,&y); g[x].push_back(y); g[y].push_back(x); } vis[1]=1; dfs(1); printf("%d\n",ans.size()); if(ans.size()==1) { printf("%d",ans[0]); } else { printf("%d\n%d",min(ans[0],ans[1]),max(ans[0],ans[1])); } }

树的直径

概念

给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点(两个节点肯定都是叶子节点)之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径。

题目描述

给定一个有个节点的树，树以个点条边的无向图形式给出， 求树的直径。 输入格式 输入的第1行为包含了一个正整数，为这棵二叉树的结点数。 接下来N行，每行有个正整数，表示有一条从到的无向边。 输出格式 输出包括1个正整数，为这棵二叉树的直径。 样例 样例输入 10 1 2 1 3 2 4 4 5 4 6 1 7 5 8 7 9 7 10 样例输出 6

分析

跑2个dfs，第一个求以根为起点的最短距离，第二个求一最长距离终点为起点的最长距离，ans为第二个

#include <bits/stdc++.h> using namespace std; int n; int x, y; vector<int> g[100005]; int dp[1000005]; int ans; int jl; void dfs(int x, int fa) { if (ans < dp[x]) { ans = dp[x]; jl = x; } for (int i = 0; i < g[x].size(); i++) { int v = g[x][i]; if (v == fa) { continue; } dp[v] = dp[x] + 1; dfs(v, x); } } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { scanf("%d %d", &x, &y); g[x].push_back(y); g[y].push_back(x); } ans = 0; dp[1] = 0; dfs(1, 0); ans = 0; dp[jl] = 0; dfs(jl, 0); printf("%d", ans); }