旅游

入门树形DP

做法

设为第个点住宿/不住宿的最大时间，随便转移一下就行了。

CODE

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define lowbit(x) x & -x
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
I int read() {
    int s = 0 , w = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
    while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
    return s * w;
}
const int N = 1e6 + 5;

int n , s , head[N] , tot , f[N][2];

struct Edge{
    int to , nxt; 
} e[N << 1];

I void addedge(int x , int y) {
    e[++ tot] = (Edge) {y , head[x]} , head[x] = tot;
}

void dfs(int u , int par) {
    f[u][0] = 0 ; f[u][1] = 1;
    for(int i = head[u] ; i ; i = e[i].nxt) {
        int v = e[i].to;
        if(v == par) continue;
        dfs(v , u);
        f[u][0] += max(f[v][1] , f[v][0]);
        f[u][1] += f[v][0];
    }
}
signed main() {
    n = read() , s = read();
    For(i , 1 , n - 1) {
        int u = read() , v = read() ; 
        addedge(u , v) ; addedge(v , u);
    }
    dfs(s , s);
    cout << f[s][1] << endl;
    return 0;
}