简单解题思路

问题描述

给定一个树形结构（森林），每个节点有两个属性：

1. num：表示该节点的初始值
2. q：表示该节点的子节点列表

要求计算将所有节点的值调整为1所需的最小操作次数。每次操作可以将一个节点的值+1或-1，并且这个操作会沿着树向上传递影响父节点。

核心思想

1. 树形结构处理：

   • 使用邻接表que存储树的父子关系
   • 数组rd记录每个节点的入度（用于找根节点）
   • 数组num存储每个节点的初始值

2. 深度优先搜索（DFS）：

   • 从根节点开始递归处理
   • 对于每个节点，先处理其所有子节点
   • 累计子节点的值到当前节点
   • 计算并累加调整子节点所需的操作次数（绝对值）
   • 最后将当前节点的值减1（因为每个节点最终需要调整为1）

3. 结果计算：

   • 所有操作次数的累加和即为最终答案

关键步骤

1. 初始化：

   • 清空邻接表
   • 重置节点值和入度

2. 输入处理：

   • 读取每个节点的初始值和子节点列表
   • 构建树形结构并记录入度

3. DFS遍历：

   • 从入度为0的根节点开始遍历
   • 递归处理每个子树
   • 累计操作次数

4. 输出结果：

   • 打印总操作次数

算法特点

• 时间复杂度：O(n)，每个节点只访问一次
• 空间复杂度：O(n)，使用邻接表存储树结构
• 适用场景：树形结构的平衡调整问题

优化说明

• 使用DFS避免重复计算
• 利用入度数组快速定位根节点
• 递归过程中实时更新和传递节点值

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

const int M = 10005;
vector<int>que[M];
int num[M];
int rd[M];
int n, ans;

void init() {
	
	for(int i = 0; i <= n; i++){
		
		que[i].clear();
		num[i] = 0;
		rd[i] = 0;
	}
}

void dfs(int u){
	
	int v;
	for(int i = 0; i < (int)que[u].size(); i++) {
		
		v = que[u][i];
		dfs(v);
		num[u] += num[v];
		ans += fabs(num[v]);
	}
	num[u] -= 1;
}

int main()
{
	int a, b, q;
	
	while(scanf("%d", &n) != EOF) {
		
		if(!n)
			break;
		init();
		ans = 0;
		for(int i = 0; i< n; i++){
			
			scanf("%d%d%d", &a, &b, &q);
			num[a] = b;
			for(int j = 0; j < q; j++){
				
				scanf("%d", &b);
				que[a].push_back(b);
				rd[b]++;
			}
			
		}
		for(int i = 1; i <= n; i++){
			
			if(!rd[i]){
				
				dfs(i);
				break;
			}
		}
		printf("%d\n", ans);
	}
	
	return 0;
}