[CSP-S模拟测试]:beauty（搜索）

题目描述

距离产生美。
一棵包含$n$个点的树，有$2k$个不同的关键点，我们现在需要将这些点两两配对，对于一种形如：
$$(u_1,v_1),(u_2,v_2),...,(u_k,v_k)$$
的配对方案，我们定义其美丽值为：
$$beauty=\sum \limits_{i=1}^k dist(u_i,v_i)$$
（其中$dist(u,v)$表示点$u$到$v$的简单路径的边数）。
现在，请你找出美丽值最大的配对方案的美丽值。

输入格式

第一行包含三个整数$n,k,a$其中$a$为$1$表示有特殊性质，$a$为$0$表示没有特殊性质。
第二行包含$2k$个不同整数$u_1,u_2,...,u_{2k}$，表示关键点。
接下来$-1$行每行包含两个整数$u,v$，表示一条边。

输出格式

输出一行，包含一个整数表示最大的$beauty$值。

样例

样例输入：

7 2 0
1 5 6 2
1 3
3 2
4 5
3 7
4 3
4 6

样例输出：

数据范围与提示

样例解释：

样例解释：$(1,6),(2,5)$这种配对方案美丽值最大，为$6(dist(1,6)+dist(2,5)=3+3=6)$。

数据范围：

特殊性质：每个点的度数小于等于$2$
对于所有数据：$1\leqslant u_i,v_i\leqslant n$且$1\leqslant u,v\leqslant n$。

题解

我们用$dp[u]$表示走到$u$这个节点的边最多是多少条，从$u$走到它父亲的边是$min(dp[u],2k-size[u])$，其中$size[u]$表示$u$这棵子树中的关键点数量，$min$的前面一项是$u$最多能提供的条数，后面一项是外面最多能接收的条数，两者较小值即为从$u$到其父亲最多的条数,我们只需要最后统计一下经过每条边的条数的和即可。
时间复杂度：$\Theta(n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int nxt,to;}e[200000];

int head[100001],cnt;

int n,k,a;

int size[100001];

bool u[100001],vis[100001];

long long ans;

void add(int x,int y)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	head[x]=cnt;

}

void dfs(int x)

{

	if(u[x])size[x]=1;

	vis[x]=1;

	for(int i=head[x];i;i=e[i].nxt)

		if(!vis[e[i].to])

		{

			dfs(e[i].to);

			size[x]+=size[e[i].to];

		}

	ans+=min(size[x],(k<<1)-size[x]);

}

int main()

{

	scanf("%d%d%d",&n,&k,&a);

	for(int i=1;i<=(k<<1);i++){int x;scanf("%d",&x);u[x]=1;}

	for(int i=1;i<n;i++){int x,y;scanf("%d%d",&x,&y);add(x,y);add(y,x);}

	dfs(1);printf("%d",ans);

	return 0;

}

rp++

巴特西