题解 | #小绿的房子#

简单的分类讨论，存储每个结点的父亲fa[i]，深度dep[i]；整棵树的最大深度maxndep；以及深度为i的结点的集合mem[i]

#include<iostream>
#include<vector>
using namespace std;

const int N = 1e5 + 5;
int fa[N], dep[N], maxndep, ans;
vector<int> mem[N], nxt[N];

void build(int idx, int f)
{
	for (int i = 0; i < nxt[idx].size(); i++)
	{
		if (nxt[idx][i] != f)
		{
			fa[nxt[idx][i]] = idx;
			dep[nxt[idx][i]] = dep[idx] + 1;
			mem[dep[idx] + 1].push_back(nxt[idx][i]);
			maxndep = max(maxndep, dep[idx] + 1);
			build(nxt[idx][i], idx);
		}
	}
}

int main()
{
	int n; cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b; cin >> a >> b;
		nxt[a].push_back(b);
		nxt[b].push_back(a);
	}
	dep[1] = 1; mem[1].push_back(1); build(1, 0);
}

另外先看第三层所有结点的父亲是否相同(samefa3)

samefa4同理。后面有用

bool samefa3 = true, samefa4 = true;
if (maxndep < 3) samefa3 = false;
if (maxndep < 4) samefa4 = false;
for (int i = 1; i < mem[3].size(); i++)
{
	if (fa[mem[3][i]] != fa[mem[3][0]])
	{
		samefa3 = false; break;
	}
}
for (int i = 1; i < mem[4].size(); i++)
{
	if (fa[mem[4][i]] != fa[mem[4][0]])
	{
		samefa4 = false; break;
	}
}

易知只有深度为1或2或3的结点有可能成为符合要求的结点。

对于第一层的结点(即根结点)，只要maxndep <= 3, 它就是符合要求的。

if (maxndep <= 3)
{
	ans += mem[1].size();
}

对于第二层的结点a，它到第一层的距离一定是1，因为第一层只有一个结点；第二层的结点之间的距离一定是2；而它到第三层结点b的距离有两种情况：一、a是b的父亲，距离为1 二、a不是b的父亲，距离为3

因此当maxndep == 2时，第二层所有结点均满足要求

if (maxndep == 2)
{
	ans += mem[2].size();
}

当3 <= maxndep <= 4时，如果第三层的所有结点的父亲都相同，那么那个父亲结点满足要求。否则第二层就没有满足要求的点了。

else if (maxndep <= 4 && samefa3)
{
	ans += 1;
}

对于第三层的结点，分析方法和第二层的一样。唯一不同的是第一层一定只有1个结点，但第二层不一样，要加一个判断条件

if (maxndep == 3 && mem[2].size() == 1)
{
	ans += mem[3].size();
}
else if (maxndep <= 5 && mem[2].size() == 1 && samefa4)
{
	ans += 1;
}