题目链接  

题意  给定一棵树，现在要加一条连接$1$（根结点）和$x$的边，求加了这条边之后，所有点到根结点的距离的和的最小值。

　　  输出这个最小值即可。

 

当加的这条边为$1-x$时，$x$和$1$的中点及以下的所有点到根结点的距离都发生了变化，其他点都没有发生改变。

现在设$ans[i]$表示当加的这条边为$1-x$时的答案，考虑答案从某个点转移到他的儿子。

首先树型DP预处理出$ans[1]$。

当$x$为$1$的儿子的时候，这时加的边为重边，所以$ans[x] = ans[1]$。

在处理的时候设$c[dep]$为当前深度为$dep$的点。

其他时候，令$x$和$1$的中点为$u$，这个时候$x$和$x$的父亲相比，以$u$为根的子树这个部分到$1$的距离要加$1$（更远了）。

但是有一部分的点例外，那就是以$x$为根的子树，直接通过$x$到$1$，而不是通过$x$的父亲到$1$。

所以考虑刚刚加的$1$，这一部分的值要减$2$。

时间复杂度$O(n)$

 

#include 
     
      using namespace std;#define rep(i, a, b)	for (int i(a); i <= (b); ++i)#define dec(i, a, b)	for (int i(a); i >= (b); --i)typedef long long LL;const int N = 2e5 + 10;int T, n;int sz[N], deep[N];int c[N];LL  f[N];LL  ans[N], all, ret;vector 
      
        v[N];void dfs(int x, int fa, int dep){	sz[x]   = 1;	f[x]    = 0;	deep[x] = dep;	for (auto u : v[x]){		if (u == fa) continue;		dfs(u, x, dep + 1);		sz[x] += sz[u];		f[x]  += 0ll + f[u] + sz[u];	}}void solve(int x, int fa, int dep){	for (auto u : v[x]){		if (u == fa) continue;		c[dep] = u;		if (deep[u] >= 2) ans[u] = ans[x] + sz[c[dep / 2 + 1]] - 2 * sz[u];		else ans[u] = ans[x];		solve(u, x, dep + 1);	}}		int main(){	scanf("%d", &T);	while (T--){		scanf("%d", &n);		rep(i, 0, n + 1) v[i].clear();		rep(i, 2, n){			int x, y;			scanf("%d%d", &x, &y);			v[x].push_back(y);			v[y].push_back(x);		}		dfs(1, 0, 0);		ans[1] = f[1];		c[0] = 0;		solve(1, 0, 1);		ret = ans[1];		rep(i, 2, n) ret = min(ret, ans[i]);		printf("%lld\n", ret);	}	return 0;}