bin哥表示，此题难度根本没有那么高，应该是蓝题或者绿题。
当然像我这样的juruo自己没想出来，听了bin哥的讲解。
其实想法很简单，我们用dp[i]表示在i节点出能得到的最大的毛毛虫的大小。因为我们要保证只有一条链，所以其实DP值只能从i节点所有的子节点中找一个DP值最大的进行更新，就是dp值加上i节点的点度-1.不过答案不需要，答案是可以把两条链拼接起来的，所以我们同时维护一个最大值和一个次大值进行转移即可。
这种做法是dp[i]不带有自己的，然后我想让dp[i]带有自己这个点，之后进行了一波小转化，但是wa了，后来发现原因是更新答案的时候，答案有可能不是在你选择的那个根取得的，所以改了一下，只有在根的位置更新答案-1，其他都不变（算上父亲）
看一下两种代码。
bin哥的：
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 300005; const int N = 20005; const int INF = 1000000009; const double eps = 1e-4; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to; }e[M<<1]; int n,m,x,y,dp[M],ans,ecnt,head[M],deg[M],son[M]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void dfs(int x,int fa) { int maxn = 0,maxx = 0; for(int i = head[x];i;i = e[i].next) { if(e[i].to == fa) continue; dfs(e[i].to,x); dp[x] = max(dp[x],dp[e[i].to] + deg[x] - 1); if(dp[e[i].to] > maxn) maxx = maxn,maxn = dp[e[i].to]; else if(dp[e[i].to] > maxx) maxx = dp[e[i].to]; } ans = max(ans,maxn + maxx + deg[x] - 1); } int main() { n = read(),m = read(); rep(i,1,m) x = read(),y = read(),add(x,y),add(y,x),deg[x]++,deg[y]++; rep(i,1,n) dp[i] = 1; dfs(1,1); //rep(i,1,n) printf("%d ",dp[i]);enter; printf("%d ",ans); return 0; }
我魔改的：
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 300005; const int N = 20005; const int INF = 1000000009; const double eps = 1e-4; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } struct edge { int next,to; }e[M<<1]; int n,m,x,y,dp[M],ans,ecnt,head[M],deg[M],son[M]; void add(int x,int y) { e[++ecnt].to = y; e[ecnt].next = head[x]; head[x] = ecnt; } void dfs(int x,int fa) { int maxn = 0,maxx = 0; for(int i = head[x];i;i = e[i].next) { if(e[i].to == fa) continue; dfs(e[i].to,x); son[x]++; } for(int i = head[x];i;i = e[i].next) { dp[x] = max(dp[x],dp[e[i].to] + son[x]); if(dp[e[i].to] > maxn) maxx = maxn,maxn = dp[e[i].to]; else if(dp[e[i].to] > maxx) maxx = dp[e[i].to]; } if(x != 1) ans = max(ans,maxn + maxx + son[x]); else ans = max(ans,maxn + maxx + son[x] - 1); } int main() { n = read(),m = read(); rep(i,1,m) x = read(),y = read(),add(x,y),add(y,x),deg[x]++,deg[y]++; rep(i,1,n) dp[i] = 1; dfs(1,1); //rep(i,1,n) printf("%d ",dp[i]);enter; printf("%d ",ans); return 0; }