Comment

232202 赵尧鹏: 2024-02-04 22:16:50
下面是一个错误答案，有大佬帮忙看下吗？


#include<iostream>
#include<algorithm>
#include<vector>


class Node	// 树的节点类，包含唯一标识该节点的nodeId和用于存放后代id的children数组
{
public:

	std::vector<int> children;
	int nodeId = -1;	//该值为-1时，代表已遍历；该值>-1时，代表节点id号

	Node() {};

	void addChild(int childId)
	{
		children.push_back(childId);
	}

	void clear() 
	{
		children.clear();
	}

};

Node* nodeArray = new Node[50000];

struct dfsRet {		//默认节点涂白色的结果(wRet)和涂黑色的结果(bRet)
	int wRet = 0;
	int bRet = 1;
};

dfsRet dfs(Node* nodePtr)	//深度搜索，每个节点只会被遍历一次，复杂度为O(n)
{
	dfsRet ret;
	nodePtr->nodeId = -1;	//遍历一个节点时，将nodeId置为-1代表该节点已经遍历，避免被子节点重复遍历
	std::vector<int> children = nodePtr->children;

	for(int i=0; i<children.size(); i++)
	{
		Node* childNode = &nodeArray[children[i]];
		if (childNode->nodeId != -1) {	//检查该子节点是否已经遍历
			dfsRet childRet = dfs(childNode);

			//节点涂黑色的结果 = 1 + 子节点均涂白色的结果（因为黑后面只能涂白）
			ret.bRet += childRet.wRet;		
			
			//节点涂白色的结果 = 0 + 每个子节点涂色的最大值的和（白后面可黑可白）
			ret.wRet += std::max(childRet.bRet, childRet.wRet);		
		}
	}
	nodePtr->clear();	//清空children数组（一个节点只会访问一次，遍历后数组已无用）
	return ret;
}

int main() 
{
	int T;
	std::cin >> T;
	for (int i=0; i < T; i++)
	{
		int nodeNum;
		std::cin >> nodeNum;
		for (int j = 0; j < nodeNum; j++)	//将需遍历的节点id置为正数（正数代表未遍历、-1代表已遍历）
			nodeArray[j].nodeId = j;
		for (int j = 0; j < nodeNum - 1; j++)
		{
			int u, v;
			std::cin >> u >> v;

			// 无向图，互为子节点。后续通过nodeId避免重复遍历
			nodeArray[u - 1].addChild(v - 1);
			nodeArray[v - 1].addChild(u - 1);
		}
		dfsRet ret = dfs(nodeArray);
		std::cout << (int)std::max(ret.bRet, ret.wRet) << std::endl;
	}
	delete[] nodeArray;
	return 0;
}