ABC-394-F-Alkane（烷烃） · znzryb
## 思路讲解
这个下面的题目好像是问怎么把一个图转化为雪花树
[ABC-385-E - Snowflake Tree](/2025/01/31/20250131-4f5a5fac)
这个是要问Alkane的最大子图（边数最多）
给的无向图是一颗树。
> “烷烃”的定义是这颗树上，顶点的入度为4或者为1，而且必须有一个点的入度为4
其实我感觉这种题目，这种比较简单的树上dp没什么难的，就是要分类讨论，每种情况都要想清楚。
## AC代码
[https://atcoder.jp/contests/abc394/submissions/64007396](https://atcoder.jp/contests/abc394/submissions/64007396)
```cpp
// Problem: F - Alkane
// Contest: AtCoder - KAJIMA CORPORATION CONTEST 2025 (AtCoder Beginner Contest 394)
// URL: https://atcoder.jp/contests/abc394/tasks/abc394_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
typedef pair<ll,bool> plb;
ll N,M,T,A[MAXN];
vector<ll> g[MAXN];
ll ans=0;
bool vis[MAXN];
ll dp[MAXN];
pair<ll,bool> dfs(ll x){
ll lans=0;
bool flag=false;
vector<ll> rett;
FOR(i,0,SZ(g[x])-1){
ll node=g[x][i];
if(!vis[node]){
vis[node]=true;
plb ret=dfs(node);
if(ret.se) flag=true;
lans+=ret.fi;
rett.pb(ret.fi);
}
}
if(SZ(g[x])==4){
lans+=1;
ans=max(lans,ans);
return (plb){lans,true};
}else if(SZ(g[x])==1){
lans+=1;
if(flag) ans=max(lans,ans);
return (plb){lans,flag};
}else if(SZ(g[x])<4){
if(flag){
sort(all(rett));
ans=max(ans,1+rett[SZ(rett)-1]);
}
return (plb){1,false};
}else{
sort(all(rett));
lans=0;
ROF(i,SZ(rett)-1,SZ(rett)-3){
lans+=rett[i];
}
lans+=1;
ans=max(ans,lans+rett[SZ(rett)-4]);
return (plb){lans,true};
}
}
inline void solve(){
cin>>N;
ans=0;
FOR(i,1,N-1){
ll a,b;
cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
vis[1]=true;
dfs(1);
cout<<(ans==0?-1:ans)<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
/*
WA
http://atcoder.jp/contests/abc394/submissions/64001178
AC
https://atcoder.jp/contests/abc394/submissions/64007396
*/
```
## 心路历程（WA，TLE，MLE……）
```cpp
7
1 2
2 3
3 4
3 5
3 6
3 7
ans: 5
8
1 2
2 3
3 4
3 5
5 6
5 7
5 8
ans:5
hack: https://atcoder.jp/contests/abc394/submissions/64007220
该提交在入度为2or3的处理上有一点问题
```
hack数据以上
```cpp
// Problem: F - Alkane
// Contest: AtCoder - KAJIMA CORPORATION CONTEST 2025 (AtCoder Beginner Contest 394)
// URL: https://atcoder.jp/contests/abc394/tasks/abc394_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
constexpr ll MAXN=static_cast<ll>(2e5)+10,INF=static_cast<ll>(5e18)+3;
typedef pair<ll,bool> plb;
ll N,M,T,A[MAXN];
vector<ll> g[MAXN];
ll ans=0;
bool vis[MAXN];
pair<ll,bool> dfs(ll x){
ll lans=0;
bool flag=false;
FOR(i,0,SZ(g[x])-1){
ll node=g[x][i];
if(!vis[node]){
vis[node]=true;
plb ret=dfs(node);
if(ret.se) flag=true;
lans+=ret.fi;
}
}
if(SZ(g[x])==4){
lans+=1;
#ifdef LOCAL
cerr << x<<" "<<lans << '\n';
#endif
ans=max(lans,ans);
return (plb){lans,true};
}else if(SZ(g[x])==1){
lans+=1;
#ifdef LOCAL
cerr << x<<" "<<lans << '\n';
#endif
if(flag) ans=max(lans,ans);
return (plb){lans,flag};
}else{
return (plb){1,false};
}
}
inline void solve(){
cin>>N;
ans=0;
FOR(i,1,N-1){
ll a,b;
cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
vis[1]=true;
dfs(1);
cout<<(ans==0?-1:ans)<<"\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
solve();
return 0;
}
/*
WA
http://atcoder.jp/contests/abc394/submissions/64001178
*/
```