标签：子树 int 路径 dfs 树形 ans 节点 dp

含义

---

顾名思义，在树上dp，一般要分类讨论，在dfs中做dp

 

没有上司的舞会

---

https://www.luogu.com.cn/problem/P1352

 

Ural 大学有 N 名职员，编号为 1∼N。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数 Hi 给出，其中 1≤i≤N。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

输入格式

 

第一行一个整数 N。

接下来 N 行，第 i 行表示 i 号职员的快乐指数 H[i]。

接下来 N−1 行，每行输入一对整数 L,K，表示 L是 K 的直接上司。

1≤N≤6000,

−128≤H[i]≤127

 

输出格式

 

输出最大的快乐指数。

 

输入/输出例子1

输入：

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

 

输出：

5

 

样例解释

无

 

 

考虑分类讨论，某个节点去和不去，那么会对这个节点的子树造成一定影响

f[i][0/1]: 表示以i为根的子树 (节点i ) 去(1) 或 不去(0) 的点权最大值

由于每个以i为根的子树对i的贡献是相互独立的，所以分每个子树进行讨论，我们只需要知道一颗子树如何转移，另外的子树同理

设v是u的子树，转移方程显而易见

f[u][0]+=max(f[v][1], f[v][0])       //u节点不去，v节点可去可不去
f[u][1]+=f[v][0]      //u节点不去，v节点绝对不能去

初始化时，f[u][1]=h[u]，即当u节点去时，最大值先假设为他自己的权值

 

#include <bits/stdc++.h>
using namespace std;
const int N=6005;

int n, h[N], u1, v1, root, f[N][3];
vector<int> a[N];
bool d[N];
void dfs(int u, int fa)
{
	f[u][1]=h[u];
	f[u][0]=0;
	
	for (int i=0; i<a[u].size(); i++)
	{
		int v=a[u][i];
		if (v==fa) continue;
		dfs(v, u);
		
		f[u][1]+=f[v][0];
		f[u][0]+=max(f[v][1], f[v][0]);
	}
}
int main()
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%d", &h[i]);
	
	for (int i=1; i<n; i++)
	{
		scanf("%d%d", &u1, &v1);
		a[v1].push_back(u1);
		d[u1]=1;
	}
	
	for (int i=1; i<=n; i++) 
		if (!d[i])
		{
			root=i;
			break;
		}
	
	dfs(root, -1);
	
	printf("%d", max(f[root][0], f[root][1]));
	return 0;
}

　　

 

 

树的最长直径

---

给定一棵树，树中包含 n 个结点（编号1~n）和 n−1 条无向边，每条边都有一个权值。

现在请你找到树中的一条最长路径。

换句话说，要找到一条路径，使得路径两端的点的距离最远。

注意：路径中可以只包含一个点。

输入格式

 

第一行包含整数 n。

接下来 n−1 行，每行包含三个整数 a[i],b[i],c[i]，表示点 a[i] 和 b[i] 之间存在一条权值为 c[i] 的边。

1≤n≤10000,

1≤a[i],b[i]≤n,

−1e5≤ci≤1e5

 

输出格式

 

输出一个整数，表示树的最长路径的长度。

 

输入/输出例子1

输入：

6

5 1 6

1 4 5

6 3 9

2 6 8

6 1 7

 

输出：

22

 

样例解释

无

 

暴力

---

 （别人的代码，将就着看着吧）

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, M = N << 1;
// 　暴力搜索，从每个节点为根出发，遍历整根树，找出距离自己的最大距离,然后每个最大距离取min
//   11/17,其它TLE,无法AC
int n;
int ans; // 树的直径
// 邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int u, int fa, int sum) {
    if (sum > ans) ans = sum;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue; // 不走回头路
        dfs(v, u, sum + w[i]);
    }
}

int main() {
    // 初始化邻接表
    memset(h, -1, sizeof h);

    cin >> n;
    for (int i = 1; i < n; i++) { // n-1条边
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c); // 无向图
    }

    // 多次dfs,是TLE的罪魁祸首
    for (int i = 1; i <= n; i++) dfs(i, 0, 0);

    // 输出结果
    printf("%d", ans);
    return 0;
}

　　

两次解法dfs

---

优点：思路简单

缺点：只适用于不带负边的树

 传送门1号   传送门2号

 （别人的代码）

#include <bits/stdc++.h>

using namespace std;

const int N = 10010, M = N << 1;

int ans; // 保存最长路径
int t;   // 保存找到的最远点
int n;

// 邻接表
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

void dfs(int u, int fa, int sum) {
    if (sum > ans) {
        ans = sum; // 记录最大距离
        t = u;     // 记录最远的点t1
    }
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        dfs(v, u, sum + w[i]);
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    dfs(1, 0, 0); // 先找到点距离点1最远的点t1

    dfs(t, 0, 0); // 找到距离点t1->t2最远的点t1

    printf("%d", ans);
    return 0;
}

　　

 

最长+次长解法

---

树的最长路径 ，也称为树的 直径 ,直径 不唯一

我们知道：树上 任意两点 的路径是 唯一 确定的，因此我们可以暴力枚举 起点 和 终点 找出最长路径

如果这样做的话，我们来思考一下时间复杂度：

 

这里找出两点之间的路径有很多种做法，预处理 st 表然后倍增求LCA、树链剖分、Link-Cut Tree

 

 

 本图中f[x]表示x的子节点到x的最长距离,而非以x为顶点的最长路径.因为本题的路径是两条边,所以f[x]表示其中一条边的最大的值,f[y],f[z]同理,两条边加起来即为以u为顶点最长路径

 注:本题的答案不一定为以u为顶点的路径,因为u到x,y,z的距离可能均为负数,所以答案可以是以x,y或者z为顶点的路径
本题采用dfs的方法来求解,所以是求解方式自下而上的

 

 

补充

 

 

#include <bits/stdc++.h>
using namespace std;
const int N=10005;

struct node
{
	int v, w;
};
int n, u1, v1, w1, root=0, dis[N], dis2[N], ans=0;
bool d[N];
vector<node> a[N];
void dfs(int u, int fa)
{
	for (int i=0; i<a[u].size(); i++)
	{
		int v=a[u][i].v, w=a[u][i].w;
		if (v==fa) continue;
		dfs(v, u);
		
		int x=dis[v]+w;
		if (dis[u]<=x) dis2[u]=dis[u], dis[u]=x;
		else if (dis2[u]<x) dis2[u]=x;
	}
	ans=max(ans, dis[u]+dis2[u]);
}
int main()
{
	scanf("%d", &n);
	for (int i=1; i<n; i++)
	{
		scanf("%d%d%d", &u1, &v1, &w1);
		a[u1].push_back({v1, w1});
		a[v1].push_back({u1, w1});
		
		d[v1]=1;
	}
	
	for (int i=1; i<=n; i++)
		if (!d[i])
		{
			root=i;
			break;
		}
	
	dfs(root, -1);
	
	printf("%d", ans);
	return 0;
}

　　

 参考：

https://www.cnblogs.com/littlehb/p/15784687.html

https://blog.csdn.net/qq_45896050/article/details/122777766

 

 

 

 

 

 

 

 

 

 

标签：子树,int,路径,dfs,树形,ans,节点,dp
From： https://www.cnblogs.com/didiao233/p/18316683