思路

很容易想到是

树形DP

如果树形DP不知道是什么的话推荐百度一下

我在这里用vector储存边

设状态f[i][0]为i点不访问，f[i][1]为i点访问

那么f[u][1] += f[y][0]表示u点要访问，(u,y)有连边
f[u][0] += max(f[v][0], f[v][1])表示u点不访问，(u,y)有连边

上面就是我们的转移方程了

介绍一下vector吧

vector是STL里的一个向量容器

也叫动态数组

就是不定长的数组

用来储存边非常好用

因此我在这里用vector给大家演示一下

代码

 1 #include<bits/stdc++.h>//万能头
 2 #define ll long long//作废
 3 using namespace std;//标准头
 4 #define N 50005
 5 int f[N][2];//DP
 6 vector<int>son[N];//建图
 7 bool v[N];//标记是否访问
 8 inline int read() {
 9     int f = 1, x = 0; char ch;
10     do { ch = getchar(); if (ch == '-')f = -1; } while (ch<'0' || ch>'9');
11     do { x = x * 10 + ch - '0'; ch = getchar(); } while (ch >= '0'&&ch <= '9');
12     return f * x;
13 }//读入优化 不解释
14 int dp(int u)//以u为根节点
15 {
16     f[u][1] = 1;//初始值1
17     for (int i=0;i<son[u].size();i++)//用vector访问每一个点
18     {
19         int y=son[u][i];//y为下一个要搜的点 即子节点
20         if(!v[y]) //如果子节点没被访问
21         {
22             v[y]=true;//标记
23             dp(y);//递归访问
24             f[u][0]+=max(f[y][0],f[y][1]); //转移方程 上面有解释
25             f[u][1]+=f[y][0];
26         }
27     }
28 }
29 int main()
30 {
31     int n=read();
32     for(int i=1;i<n;i++)
33     {
34         int x=read(),y=read();
35         son[x].push_back(y);//用vector建边
36         son[y].push_back(x);
37     }
38     memset(v,0,sizeof(v));memset(f,0,sizeof(f));
39     v[1]=true;//初始值
40     dp(1);//以1为根
41     printf("%d
",max(f[1][1],f[1][0])); //输出
42     return 0;
43 }