题解：AT_abc394_f [ABC394F] Alkane
Emplace
·
·
题解
思路
这道题是一个树形 DP。
状态
### 初始化
$dp_{u,0}$ 是 $1$ 就是它本身。其它的就为无穷小。
### 转移方程
$dp_{u,i}=max(dp_{u,i},dp_{u,i-1}+max(dp_{v,0},dp_{v,3}))$。
也就是说它可以选择加这个儿子或不加。要加的话就必须从儿子有三个或零个子节点中选，不然就不满足要求。由此可以推出此方程
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,h[414514],e[414514],ne[414514],idx,dp[414514][5],mx=-1;
void add(int u,int v){
e[idx]=v,ne[idx]=h[u],h[u]=idx++;
}
void dfs(int u,int pre){
dp[u][1]=-0x3f3f3f3f,dp[u][2]=-0x3f3f3f3f,dp[u][3]=-0x3f3f3f3f,dp[u][4]=-0x3f3f3f3f;
dp[u][0]=1;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(j==pre){
continue;
}
dfs(j,u);
for(int i=4;i>=1;i--){
dp[u][i]=max(dp[u][i],dp[u][i-1]+max(dp[j][0],dp[j][3]));
}
}
if(dp[u][1]>2){
mx=max(mx,dp[u][1]);
}
mx=max(mx,dp[u][4]);
}
int main(){
memset(h,-1,sizeof(h));
cin>>n;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
dfs(1,0);
cout<<mx;
return 0;
}
```