之前写在洛谷，结果没保存，作废……
听说考前写题解RP++哦
思路
很容易想到是
树形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给大家演示一下
代码
#include<bits/stdc++.h>//万能头
#define ll long long//作废
using namespace std;//标准头
#define N 50005
int f[N][];//DP
vector<int>son[N];//建图
bool v[N];//标记是否访问
inline int read() {
int f = , x = ; char ch;
do { ch = getchar(); if (ch == '-')f = -; } while (ch<'' || ch>'');
do { x = x * + ch - ''; ch = getchar(); } while (ch >= ''&&ch <= '');
return f * x;
}//读入优化 不解释
int dp(int u)//以u为根节点
{
f[u][] = ;//初始值1
for (int i=;i<son[u].size();i++)//用vector访问每一个点
{
int y=son[u][i];//y为下一个要搜的点 即子节点
if(!v[y]) //如果子节点没被访问
{
v[y]=true;//标记
dp(y);//递归访问
f[u][]+=max(f[y][],f[y][]); //转移方程 上面有解释
f[u][]+=f[y][];
}
}
}
int main()
{
int n=read();
for(int i=;i<n;i++)
{
int x=read(),y=read();
son[x].push_back(y);//用vector建边
son[y].push_back(x);
}
memset(v,,sizeof(v));memset(f,,sizeof(f));
v[]=true;//初始值
dp();//以1为根
printf("%d\n",max(f[][],f[][])); //输出
return ;
}