Comment

SoulPowering...: 2026-05-03 16:55:23

#include<iostream>
#include<cstring>
using namespace std;

const int N=50010;
// 和“上司的舞会”本质一样，状态转移一摸一样
// 只是上司题的父子关系天然给定，有一个定了的根（有向图）
// 而这题的父子关系需要通过 DFS 人为确定，根自己随便定一个（无向图）

//树的本质：连通且没有环的无向图，
//采用邻接表存储，能够直接找到以i号为根节点所有子节点（向下直接相邻的所有子节点）,
//k为l的直接，除开最上层根节点，其他n-1个点都有一个直接父节点，共n-1条边

int h[2*N],e[2*N],ne[2*N],idx;//无向图空间要开够，两倍点的数量
int n,m;
bool visited[N];
//这是与上司的核心区别，因为是无向图，双向边，
//每次遍历所有指出去的边，保证不要指向父节点
void add(int u,int v)
{
    e[idx]=v,ne[idx]=h[u],h[u]=idx++;
}

//状态表示：
//对于每个局部根节点来说，均有选或不选m_root两种，
//f[u][0]，根节点u为白色,f[u][0]=∑max(f[j][0],f[j][1]);
//f[u][1]，根节点u为黑色,f[u][1]=1+∑f[j][0];

int f[N][2];

void dfs(int u)//求解以u为根节点的树的f[u][0],f[u][1]
{
    visited[u]=true;
    f[u][1]=1;//自己染成了黑色
    for(int i=h[u];i!=-1;i=ne[i])//注意邻接表的遍历写法，不是i++
    {
        int j=e[i];
        if(!visited[j])
        {
            dfs(j);
            f[u][0]+=max(f[j][0],f[j][1]);
            f[u][1]+=f[j][0];
        }
    }
}
int main()
{
    cin>>m;
    while(m--)
    {
        cin>>n;
        //每组数据必须初始化完整，邻接表初始化idx=0，h[i]=-1
        //visited,f都必须要重新初始化（f[][0]是在原基础上叠加）
        idx=0;
        memset(h,-1,sizeof h);
        memset(f,0,sizeof f);
        memset(visited,0,sizeof visited);
        
        for(int i=1;i<=n-1;i++)
        {
            int u,v;
            cin>>u>>v;
            add(u,v),add(v,u);
        }
    
        int root=1;
        dfs(root);
        
        cout<<max(f[root][0],f[root][1])<<endl;
    }
    
    return 0;
}

beshar: 2025-11-27 19:23:03

本以为是贪心，只要取 偶数层节点数 和 奇数层节点数 中最大的就行了，结果并不是……还是回到了dp。不知道怎么构造这个想法的反例？

zysvvv: 2025-05-26 11:49:45

贴一个python代码

def dfs(u,parent):
    for v in tree[u]:
        if v==parent:
            continue
        dfs(v, u)
        dp[u][0] += max(dp[v][0], dp[v][1])
        dp[u][1] += dp[v][0]

t=int(input())
for _ in range(t):
    n=int(input())
    edges=[tuple(map(int,input().split()))for _ in range(n-1)]
    tree=[[]*(n+1)for _ in range(n+1)]
    for u,v in edges:
        tree[u].append(v)
        tree[v].append(u)
    dp=[[0,1]for _ in range(n+1)]
    dfs(1,-1) 
    print(max(dp[1][0],dp[1][1]))

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