牛客手速月赛47 F(树学的不是很到位)

题目 题意: 给定n个点的有向树，给定m个点和起点k。至多以k为起点向其他顶点连一条边，使得k到这m个点的最短距离之和最小。 思路: 赛时思路求LCA，然后如果k的深度>=LCA的深度，必须往LCA连，否则不能到达所有点；反之，k本身就可以到达所有点，我是写的连接直接儿子的重儿子，但是不对，因为有可能有长长的链，总之欠考虑了。 看了题解的思路。如果k本身可以到达所有点，需要枚举向哪个点连边，贡献的改变类似换根dp的写法。这样，k本身不能到达所有点的情况也可以用此方法实现，都是枚举。更普遍地，可以发现要么以1为根、要么以k为根，这两种情况。可以在建树时不向k连边，这样就将两个树分开，编程容易实现，之后分情况讨论即可。

1. k = 1或者m个点都在以k为根的子树内，以k为根的子树内dfs即可，贡献的改变量为 (d[x] - d[k] - 1) * sz[x]. (深度差-1)*子树大小，因为子树中所有点(属于那m个点的)都会减少深度差-1的长度。
2. k本身不能到达m个点，也是dfs，在以1为根的子树内dfs。额外花费是最短路 + 在1中m个点的数量，因为到达任何一点的深度+1，如果某个点的sz[]达不到sz[1]，不用考虑。
3. 题解的路径和写法很妙，val[x]:表示到以x为根的所有m个点的距离和。val[cur] += val[son] + sz[son]，当前节点的距离和是儿子节点的距离和 + 子树的大小。因为子树中每个点的深度会+1的。递归求解。其实相当于起点到所有点的看一下深度差，但是这样写说明对递归理解的很到位。 时间复杂度: O(n) 代码:

#include
using namespace std;
#define mem(a,x) memset(a,x,sizeof(a))
typedef long long ll;
typedef pair PII;
const int N = 2e5+10;
int n,m,k,T;
int h[N],e[N],ne[N],idx = 0;
void add(int a,int b)
{
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
PII ee[N];
int dist[N];
int q[N];
int sz[N];
int cnt[N];
int d[N]; //深度
ll val[N];
void dfs(int cur)
{
	if(cnt[cur]) sz[cur] = 1;
	for(int i=h[cur];~i;i=ne[i])
	{
		int j = e[i];
		d[j] = d[cur] + 1;
		dfs(j);
		sz[cur] += sz[j];
		val[cur] += val[j] + sz[j];
	}
}
ll dfs2(int cur)
{
	if(sz[cur] != sz[1]) return 1e18;
	ll ans = val[cur];
	for(int i=h[cur];~i;i=ne[i])
	{
		int j = e[i];
		ans = min(ans,dfs2(j));
	}
	return ans;
}
ll dfs3(int cur)
{
	ll ans = 1ll*(d[cur] - d[k] - 1) * sz[cur];
	for(int i=h[cur];~i;i=ne[i])
	{
		int j = e[i];
		ans = min(ans,dfs3(j));
	}
	return ans;
}
void solve()
{
	cin>>n; mem(h,-1); mem(dist,0x3f);
	for(int i=0;i>ee[i].first>>ee[i].second;
	}
	cin>>m>>k;
	for(int i=0;iq[i],cnt[q[i]]++;
	dfs(1);
	if(k != 1) dfs(k);
	ll ans;
	if(sz[1] == 0 || k == 1) //所有点都在以k为根的子树中
	{
		ans = val[k] - max(0ll,dfs3(k));
	}
	else
	{
		ans = val[k] + sz[1] + dfs2(1);
	}
	cout