题目大意：给一棵树，求其中最大的“毛毛虫”，毛毛虫的定义是一条链上分出几条边

题解：把每个点的权值定义为它的度数减一，跑带权直径即可，最后答案加二

卡点：无

 

C++ Code：

#include 
     
      #include 
      
       namespace __IO {	namespace R {		int x, ch;		inline int read() {			ch = getchar();			while (isspace(ch)) ch = getchar();			for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);			return x;		}	}}using __IO::R::read;inline int max(int a, int b) {return a > b ? a : b;}#define maxn 300010int head[maxn], cnt;struct Edge {	int to, nxt;} e[maxn << 1];inline void add(int a, int b) {	e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;}int n, m;int w[maxn];int max1[maxn], max2[maxn], ans = -20040826;int dfs(int u, int fa = 0) {	for (int i = head[u]; i; i = e[i].nxt) {		int v = e[i].to;		if (v != fa) {			int tmp = dfs(v, u);			if (tmp > max1[u]) {				max2[u] = max1[u];				max1[u] = tmp;			} else if (tmp > max2[u]) max2[u] = tmp;		}	}	max1[u] += w[u];	ans = max(ans, max1[u] + max2[u]);	return max1[u];}int main() {	n = read(), m = read();	for (int i = 1, a, b; i < n; i++) {		a = read(), b = read();		add(a, b);		w[a]++, w[b]++;	}	for (int i = 1; i <= n; i++) w[i]--;	dfs(1);	printf("%d\n", ans + 2);	return 0;}