勘误：给代码加上了快读并开了 long long。

分析

看到标签里写的 dp，想了想可能是换根，但我不会，怎么办呢？

考虑什么时候会是 $-1$。观察样例发现，只有行动中心为 $2$ 的时候才不是 $-1$，而 $2$ 恰好是树的重心，那么猜想只有重心才不是 $-1$，接下来证明它。

如果一个点不是重心，那么说明至少存在其中一个子树 $T'$ 大小大于 $\frac{n}{2}$，那么剩下的子树大小之和一定小于 $\frac{n}{2}-1$，则我们每次访问完 $T'$ 中的一个节点后，要保证相邻两次不走重复道路，就需要访问一个 $T'$ 外的节点，如此到最后，会发现除了 $T'$ 中的 $2$ 个点以外其它点都访问完了，这时但凡再去访问一个点，剩下那个点就访问不到了，因此不是重心的点都是 $-1$。

做到这一步了，下一步就开始想对于重心应该输出什么。这时候，如果恰有子树 $T'$ 的节点树为 $\frac{n}{2}$，那么我们必须先访问 $T'$ 中的一个点，否则就会最后剩下 $2$ 个 $T'$ 中的点没访问，又无解了。既然需要先访问 $T'$ 中的点，那么最后必定也会剩下 $T'$ 中的点，我们想让最后这条路径尽量长（否则它要被计算两次），所以就选择 $T'$ 中深度最大的点。综上，如果重心 $c$ 存在一个子树 $T'$ 的节点个数为 $\frac{n}{2}$，答案为 $2\times\displaystyle\sum_x\operatorname{dist}(c,x)-\max_x(\operatorname{dist(c,x)}\times\{x\in T'\})$，其中 $\operatorname{dist}(i,j)$ 表示 $i,j$ 的距离，$\{x\in T'\}$ 表示 $\begin{cases} 1 &\text{if } x\in T' \\ 0 &\text{if } x\not \in T' \end{cases}$。

如果不存在这样的子树 $T'$，那么对选择没有要求，又因为 $c$ 是重心，必然存在合法解，那么最优肯定是选择深度最大的结尾，因此此时答案为 $2\times\displaystyle\sum_x\operatorname{dist}(c,x)-\max_x(\operatorname{dist(c,x)})$。

由于重心最多 $2$ 个，所以复杂度 $O(n)$。

两篇做法相同的题解都没放代码，我就放一个吧。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int maxx[N],is[N],sz[N],n,dep[N],rt,son[N],tag[N];
vector<int> G[N];
void dfs(int u,int fa)
{
	sz[u]=1;
	maxx[u]=0;
	for(auto &v:G[u])
	{
		if(v==fa) continue;
		dfs(v,u);
		sz[u]+=sz[v];
		maxx[u]=max(maxx[u],sz[v]);
		if(maxx[u]==(n>>1)&&!son[u]) son[u]=v;
	}
	maxx[u]=max(maxx[u],n-sz[u]);
	if(maxx[u]==(n>>1)&&!son[u]) son[u]=fa;
	if(maxx[u]<=(n>>1)) is[u]=1;
}
void dfs2(int u,int fa)
{
	tag[u]=(u==son[rt])|tag[fa];
	if(fa==rt) dep[u]=1;
	for(auto &v:G[u])
	{
		if(v==fa) continue;
		dep[v]=dep[u]+1;
		dfs2(v,u);
	}
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		if(!is[i]) cout<<-1<<'\n';
		else
		{
			memset(dep,0,sizeof dep);
			memset(tag,0,sizeof tag);
			rt=i;
			dfs2(i,0);
			int ans=0,maxd=0;
			for(int i=1;i<=n;i++) ans+=dep[i];
			if(!son[i])
			for(int i=1;i<=n;i++) maxd=max(maxd,dep[i]);
			else
			for(int i=1;i<=n;i++) maxd=max(maxd,dep[i]*tag[i]);
			cout<<ans*2-maxd<<'\n';
		}
	}
	return 0;
}