第十四届蓝桥杯集训——练习解题阶段(无序阶段)-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]))