题解 | 旅游

#include<bits/stdc++.h>
using namespace std;

const int MAX_N = 500005;
int n, s;
int f[MAX_N][2];  // f[x][0]不选x, f[x][1]选x
vector<int> g[MAX_N];  // 邻接表存图

void solve(int x, int fa) {
    for(int y : g[x]) {
        if(y != fa) {
            solve(y, x);
            f[x][1] += f[y][0];        // 选x时，子节点y不能选
            f[x][0] += max(f[y][0], f[y][1]);  // 不选x时，y可选可不选
        }
    }
    f[x][1]++;  // 选择当前节点，天数+1
}

int main() {
    cin >> n >> s;
    
    // 建图
    for(int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    
    solve(s, 0);
    cout << f[s][1] << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static int MAX_N = 500005;
    static int n, s;
    static int[][] f;  // f[x][0]不选x, f[x][1]选x
    static ArrayList<Integer>[] g;  // 邻接表存图
    
    static void solve(int x, int fa) {
        for(int y : g[x]) {
            if(y != fa) {
                solve(y, x);
                f[x][1] += f[y][0];        // 选x时，子节点y不能选
                f[x][0] += Math.max(f[y][0], f[y][1]);  // 不选x时，y可选可不选
            }
        }
        f[x][1]++;  // 选择当前节点，天数+1
    }
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.nextInt();
        
        // 初始化
        f = new int[MAX_N][2];
        g = new ArrayList[MAX_N];
        for(int i = 0; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        
        // 建图
        for(int i = 1; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            g[x].add(y);
            g[y].add(x);
        }
        
        solve(s, 0);
        System.out.println(f[s][1]);
        
        sc.close();
    }
}

import sys
sys.setrecursionlimit(500010)  # 扩大递归栈深度

def solve(x, fa, g, f):
    for y in g[x]:
        if y != fa:
            solve(y, x, g, f)
            f[x][1] += f[y][0]        # 选x时，子节点y不能选
            f[x][0] += max(f[y][0], f[y][1])  # 不选x时，y可选可不选
    f[x][1] += 1  # 选择当前节点，天数+1

def main():
    n, s = map(int, input().split())
    
    # 建图
    g = [[] for _ in range(n+1)]
    for _ in range(n-1):
        x, y = map(int, input().split())
        g[x].append(y)
        g[y].append(x)
    
    # f[x][0]不选x, f[x][1]选x
    f = [[0] * 2 for _ in range(n+1)]
    
    solve(s, 0, g, f)
    print(f[s][1])

if __name__ == "__main__":
    main()