Comment

lyt12345: 2024-12-18 16:35:49

树形dp
dp[i][0]记录以i为根的子树，且根为白时的最大答案，dp[i][1]是根为黑时的答案。
显然，当前为黑时，所有子节点都必须为白，当前为白时无限制，取所有子节点为黑或白时的最大值即可。
代码：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

const int N=50004;

int dp[N][2],vi[N];
int h[N],e[N*2],ne[N*2],idx;

void add(int x,int y)
{
	e[idx]=y,ne[idx]=h[x],h[x]=idx++;
}

void find(int x)
{
	vi[x]=1;
	dp[x][1]=1;dp[x][0]=0;
	for(int i=h[x];i!=-1;i=ne[i])
	{
		int y=e[i];
		if(vi[y])continue;
		find(y);
		dp[x][1]+=dp[y][0];
		dp[x][0]+=max(dp[y][0],dp[y][1]);
	}
}

int main()
{
    int T;

    cin>>T;
    while(T--)
    {
		int n;
		cin>>n;
		memset(h,-1,sizeof h);idx=0;
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			add(u,v);
			add(v,u);
		}
		memset(dp,0,sizeof dp);
		memset(vi,0,sizeof vi);
		find(1);
		cout<<max(dp[1][0],dp[1][1])<<endl;
    }
}

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;
}