第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-4 算法训练 结点选择

#include <stdio.h>
#include <string.h>
#define _Max 100010
#define max(a, b) a > b ? a : b

struct point
{
    int v, next;   //v指向这条边的另一个结点（父结点），next指向子结点
} edge[_Max * 2];  //一条边记录两次，分别以一个点做记录

int head[_Max];
int M;
int dp[_Max][2];

//添加一个边
void addEdge(int from, int to)
{
    //from结点
    edge[M].v = to;
    edge[M].next = head[from];    //为-1则定位叶结点，否则，指向另外一条边
    head[from] = M++;             //指向他的一条边，增加结点
    //to结点
    edge[M].v = from;
    edge[M].next = head[to];      //为-1则定位叶结点，否则，指向另外一条边
    head[to] = M++;               //指向他的一条边，增加结点
    return ;
}

//深度遍历，先深入到叶子结点，然后一层一层往上回升，一直到根结点，即第一个结点（初始pre为－1是因为根结点没有父结点，用－1表示）
void dfs(int x, int pre)
{
    int i = head[x], v;
    for (; i != -1; i = edge[i].next)  //i != -1说明有子结点，则遍历子结点，否则为叶子结点
    {
        v = edge[i].v;
        if (pre == v)  //如果指向的子结点和父结点重合，则说明这个结点是叶子结点，不需要进一步dp
        {
            continue;
        }
        dfs(v, x);     //x可以理解为父结点
        //深度遍历到最里面的叶子结点的父结点   如果父结点选择，则子结点不选择，否则子结点可能选择或者不选择，但是要比较两者哪个大选择哪个
        dp[x][1] += dp[v][0];                   //   父结点（选） ＋＝ 子结点（不选）
        dp[x][0] += max(dp[v][0], dp[v][1]);    //   父结点（不选） ＋＝ max（子结点（不选），子结点（选））
    }
    return ;
}
int main(int argc, const char * argv[])
{
    int i, n, s, t, tmp;
    scanf("%d", &n);
    M = 0;
    memset(head, -1, sizeof(head));   //初始化每个结点都是独立的没有子结点
    memset(dp, 0, sizeof(dp));
    //输入权值，并且记录在dp[i][1]上，i表示第i个结点，1代表取了这个结点
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &dp[i][1]);
    }
    //输入边，并且添加edge，一个边添加两个edge
    for (i = 1; i < n; i++)
    {
        scanf("%d %d", &s, &t);
        addEdge(s, t);
    }
    dfs(1, -1);   //深度优先遍历，从第一个结点开始遍历
    tmp = max(dp[1][0], dp[1][1]);    //求出最大的权值和
    printf("%d\n", tmp);
    return 0;
}

#include<stdio.h>
const int NO=1000005;
int dp[NO][2];
int du[NO];
int first[NO],next[NO],v[NO],num=1;
bool mark[NO];
int n,a;
int t[NO],tip,top;
int max(int a,int &b){return a>b?a:b;}
void input(int &num)
{
	num=0;
	char ch=getchar();
	while(ch<'0'||'9'<ch)
		ch=getchar();
	while('0'<=ch&&ch<='9')
	{
		num=10*num+ch-'0';
		ch=getchar();
	}
}
void add(int &a,int &b)
{
	v[num]=b;
	next[num]=first[a];
	first[a]=num++;
	v[num]=a;
	next[num]=first[b];
	first[b]=num++;
}
int work()
{
	int i;
	while(tip<top)
	{
		a=t[tip++];
		mark[a]=1;
		for(i=first[a];i!=-1;i=next[i])
			if(mark[v[i]])
			{
				dp[a][0]+=max(dp[v[i]][0],dp[v[i]][1]);
				dp[a][1]+=dp[v[i]][0];
			}
			else if(--du[v[i]]==1)
				t[top++]=v[i];
	}
	return max(dp[a][0],dp[a][1]);
}
int main()
{
	int i,a,b;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		input(dp[i][1]),first[i]=-1;
	for(i=1;i<n;i++)
		input(a),input(b),add(a,b),du[a]++,du[b]++;
	for(i=1;i<=n;i++)
		if(du[i]==1)
			t[top++]=i;
	printf("%d\n",work());
	return 0;
}

import java.io.IOException;
import java.util.Scanner;
import java.util.Stack;

public class Main {

	private static int[][] dp;
	private static int[][] tree;
	private static Stack<Element> stack = new Stack<>();

	static class Element {
		int start; // 节点编号
		int root; // 节点的父亲节点的编号
		int count; // 计数器，用来记录节点第count个孩子节点

		public Element(int start, int root, int count) {
			this.start = start;
			this.root = root;
			this.count = count;
		}
	}

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		dp = new int[n + 2][2];
		tree = new int[n + 2][100];

		for (int i = 0; i < n; i++) {
			dp[i + 1][1] = sc.nextInt();
		}

		for (int i = 0; i < n - 1; i++) {
			int point1 = sc.nextInt();
			int point2 = sc.nextInt();
			createTree(point1, point2);
		}
		sc.close();
		dfs2(1, 0); // 从创建的数的根节点（即第1个顶点，0表示根节点的父母节点）开始进行DFS遍历
		System.out.println(Math.max(dp[1][0], dp[1][1]));
	}

	/**
	 * @param point1 表示输入的第point1个节点，不是节点权值
	 * @param point2 表示输入的第point2的节点，不是节点权值
	 * @apiNote 由于题目仅仅给出边的说明，并未说明两个节点谁是父母节点，所以以下有两种情形
	 */
	static void createTree(int point1, int point2) {
		int i = 0;
		// 当第point1个节点为父母节点时
		while (tree[point1][i] != 0)
			i++;
		tree[point1][i] = point2; // 如果第point1个节点已经有孩子了，再增加一个孩子

		int j = 0;
		// 当第point2个节点为父母节点时
		while (tree[point2][j] != 0)
			j++;
		tree[point2][j] = point1;
	}

	/**
	 * @param start 开始对树进行DFS遍历的开始节点，为具体节点位置，不是节点权值
	 * @param root  为第start个节点的直接父母节点位置，root = 0表示根节点的父母节点
	 */
	// 老dfs，会因为递归次数过多导致系统堆栈溢出报错，导致最后三个测试案例运行错误
	static void dfs(int start, int root) {
		int child = tree[start][0]; // 第start个节点的第1个孩子节点

		for (int i = 0; child != 0; i++) {
			child = tree[start][i];
			if (child != root) // 防止出现start的孩子成为start的父亲情况
			{
				dfs(child, start);
				dp[start][1] += dp[child][0]; // 当第child个节点没有孩子节点时，开始回溯
				dp[start][0] += Math.max(dp[child][0], dp[child][1]);
			}
		}
	}

	// 新dfs，自己创建一个堆栈来存储相关信息，就不需要使用递归了，也就不会产生堆栈溢出问题
	static void dfs2(int start, int root) {
		stack.push(new Element(start, root, 0)); // 初始化第一个点压入堆栈，开始堆栈操作

		while (!stack.isEmpty()) {
			Element temp = stack.peek(); // 查看栈顶信息
			int child = tree[temp.start][temp.count]; // 找到点的孩子节点
			temp.count++; // 计数器加1
			if (child != 0) {
				if (child != temp.root) {
					stack.push(new Element(child, temp.start, 0));
					continue;
				}
			} else {
				dp[temp.root][1] += dp[temp.start][0];
				dp[temp.root][0] += Math.max(dp[temp.start][1], dp[temp.start][0]);
				stack.pop();
			}
		}
	}
}

class Vertex():
    def __init__(self,id):
        self.id=id
        self.connect=[]
        self.visited=False
    def addEdge(self,vertex):
        self.connect.append(vertex.id)

def dfs(num):
    stack=[num]
    numList[num].visited=True
    while stack:
        node = stack[-1]
        for n in numList[node].connect:
            if not numList[n].visited:
                stack.append(n)
                numList[n].visited=True
                break
        else:
            if stack.pop() != 1:
                dp[stack[-1]][0] += max(dp[node][0],dp[node][1])
                dp[stack[-1]][1] += dp[node][0]    

numList={}
n=int(input())
values = input().split()
values = [int(x) for x in values]
dp=[[0 for i in range(2)] for i in range(n+1)]
for i in range(1,n+1):
    dp[i][1]=values[i-1]
    numList[i]=Vertex(i)
for i in range(n-1):
    pre,vertex=map(int,input().split())
    numList[pre].addEdge(numList[vertex])
    numList[vertex].addEdge(numList[pre])

dfs(1)
print(max(dp[1][0],dp[1][1]))