好久没写了，水一篇

左手的ㄟ右手 2022-03-15 15:21 173阅读 0赞

# 这是一个标题 #

本来这篇的主题应该是接下来的结点选择的，但是笔者开学以来事情很多，所以那一题正确代码还没写出来，于是便跑过来诈一下尸：）

事实上，笔者的代码应该说是完成了的，我花了很长的时间去重新温习了一下结构体指针、多叉树与二叉树之间的转换、深度遍历等等知识点，因为其他博主的代码大多都是无向图，思路我没怎么看懂，委屈

几天后，就在笔者的代码接近完成的时，我的硬盘突然崩了，于是在朋友的帮助下，笔者不会承认自己不会修电脑的：）我花了一天的时间尝试修电脑，最后无奈将重要数据备份了一下，然后重买了块硬盘装，然后就是装系统，装软件，总之折腾了好久，才把我的破电脑拯救回来。

所以，到今天，就前几个小时，我好不容易把代码打完了！！！结果！系统又哔哔哔的给我报错！看了一下测试数据，才知道系统建的真哔哔哔是无向图，不是真的树！！！

而朕的代码完全是建立在它是树的基础下啊！不是树你说树干嘛？还我的头发啊啊啊！！！  
　　看过题目的读者有兴趣的话可以看一下我的代码哦，虽然是错的，但看得懂的话也是不亏的嘛~~

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h> 
    
    #define maxx 100010
    #define max(a,b) a>b?a:b
    
    struct node	//结点结构体 
    { 	int num;	//结点编号 
    	int value;	//结点的权值 
    	int childnum;	//子结点(孩子)数 
    	int parent; 	//结点的父结点 
    	struct node *child;	//结点的子结点(孩子)
    	struct node *brother;	//结点的兄弟结点 
    	struct node *p; 	//指针p指向最后一个子结点(孩子)，即子结点(孩子)的最后一个兄弟结点 
    	struct node *f;	//指针f指向第一个子结点（孩子），方便后边遍历 
    }node[maxx];
    
    int dp[maxx][2];	//max指代第 i 个结点，每个结点有取或不取两种情况，dp用于存放每一种情况的最大权值 
    
    void dfs(struct node *h)	//难点：递归 
    { 
    	int i;
    	if(h->childnum!=0)	//结点有孩子 
    	{ 
    		struct node *first=h->f;	//将指向第一个子结点的指针备份
    		 
    		for(i=0;i<h->childnum;i++)	//遍历所有子结点 
    		{ 
    			dfs(first);
    			first=first->brother; 	//遍历完第一个子结点，继续遍历下一个子结点，所以将指针移向该子结点的兄弟结点 
    		}
    	}
    	
    	for(i=0;i<h->childnum;i++)	//若没有子结点，则为叶子结点，直接跳过，其dp用一开始赋的初始值就行了 
    	{ 
    		dp[h->num][1]+=dp[h->f->num][0];	//当该结点取的时候，则子结点不取 
    		dp[h->num][0]+=max(dp[h->f->num][1],dp[h->f->num][0]);	//当该结点不取，则其子结点有两种情况，可以取，也可以不取，择最大权值 
    		h->f=h->f->brother;
    	} 
    } 
    
    int main() { 
    	int n,i,j,from,to;
    	struct node *head;	//头指针
    	scanf("%d",&n);
    	
    	for(i=1;i<=n;i++)
    	{ 
    		scanf("%d",&node[i].value);	//给每一个结点赋权值 
    		node[i].num=i;	//记下本身的编号 
    		dp[i][1]=node[i].value;	
    	}
    	
    	for(i=1;i<n;i++)
    	{ 
    		scanf("%d %d",&from,&to);
    		
    		//建树（左孩子右兄弟） 
    		if(node[from].childnum==0)	//若父结点没有子结点(孩子)，则直接将父结点的指针child指向子结点(孩子)
    		{ 
    			node[from].child=&node[to];	
    			node[from].p=&node[to];	//此时，to是 from的最后一个子结点(孩子)，所以 p指向 to 
    			node[from].f=&node[to];	
    		}
    		else	//若父结点已经有子结点（孩子），则将to作为它孩子的兄弟结点，即接在最后一个子结点（p指向的子结点）后面 
    		{ 
    			node[from].p->brother=&node[to];
    			node[from].p=&node[to];	//更新最后一个子结点 
    			
    		} 
    		
    		node[from].childnum++;	//父结点的子结点数加一 
    		node[to].parent=from;
    		
    		if(node[from].parent==0)	//如果父结点没有父（母）亲，则该结点为祖先结点（头结点） 
    			head=&node[from]; 
    	}  
    
    	//遍历树，这部分有点难懂，如果读者有自己的思路，笔者还是建议按自己的思路来 
    	dfs(head); 
    	
    	int res=max(dp[1][0],dp[1][1]);	//最终答案，前面看懂了的话这里应该就没问题了
    	printf("%d",res);
    		
    	return 0;
    }

篇后语：  
1、上面这段代码是可以优化一下的，比如结构体中的权值基本是多余的。

2、递推式和中心思想可以看其他博主的，基本一样

3、如果发生和笔者一样，电脑发生故障，记得首先想办法保住自己的数据，平时也要注意备份预防！！！**数据是无价的！！！**

4、这到题真的是无向图，**即可能不止一个头结点，一个结点可能不止一个父母结点**！！！还没写的同志千万注意！！！

5、**自己有思路的时候，最好自己写代码，自己写总比看别人的代码来得容易，且更有收获！**

5、其余我写这道题时的感悟容我留到下一篇在写，哈哈哈~~

6、对笔者的代码感兴趣的且又不懂的地方欢迎提问哦~~