之前写在洛谷，结果没保存，作废……

听说考前写题解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给大家演示一下

代码

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\n",max(f[1][1],f[1][0])); //输出 42 return 0; 43 }

 

转载于:https://www.cnblogs.com/lincold/p/9874677.html