题目链接:传送门

题目大意:n个点构成一棵树,给定 k*2 点,要分成 k 组,使每组点之间的距离之和最大。

题目思路:因为是求距离之和最大,所以我们可以知道这样一个性质。如果以一条边为界,两边的子树均有给定的点,则这条边一定会经过 min(左边的给定点数,右边的给定点数)次。

     那么这条边的贡献就是经过的次数。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include<functional>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 200005
#define maxn 10005
typedef pair<int,int> PII;
typedef long long LL; int n,m,k,a[N];
LL ans;
vector<int>V[N];
void dfs(int x,int fa){
for(int u:V[x]){
if(u==fa)continue;
dfs(u,x);
a[x]+=a[u];
ans+=min(a[u],k-a[u]);
}
}
int main(){
int i,j,group,x,y;
scanf("%d%d",&n,&k);k<<=;
for(i=;i<=k;++i){
scanf("%d",&x);
a[x]=;
}
for(i=;i<n;++i){
scanf("%d%d",&x,&y);
V[x].push_back(y);
V[y].push_back(x);
}
dfs(,-);
printf("%I64d\n",ans);
return ;
}

最新文章

  1. wxWidgets
  2. 一、JSP、servlet、SQL三者之间的数据传递(前台与后台数据交互)
  3. HDU 3032 Nim or not Nim?(sg函数)
  4. mysql连接查询语句示例
  5. robot API笔记6
  6. ASCII,Unicode 和通用方式
  7. 同一台电脑使用 gitlab 和 github 配置
  8. Linux PCI/PCI-E设备配置空间读取与修改
  9. element-- 修改MessageBox 弹框 中确定和取消按钮顺序
  10. python day04笔记总结
  11. win10 python3.5 自动补全设置
  12. bootstrap页面sidebar
  13. trinitycore 魔兽服务器源码分析(三) 多线程相关
  14. openvpn-LDAP验证
  15. js中的数据类型及判断方法
  16. JS定时器相关用法
  17. Hive权限管理
  18. 【bzoj3667】Rabin-Miller算法
  19. 蒜头君学英语--set()练习
  20. Convolutional Neural Networks for Visual Recognition 1

热门文章

  1. 小强升职记(GTD)脑图
  2. 转:SiteMesh简介
  3. js jquery 结束循环
  4. 在项目中增加自定义icon图标
  5. 修改select下拉框的下拉按钮
  6. navigate是Router类的一个方法,主要用来跳转路由。
  7. 定时检测Memcached进程是否存在,若不存在自动启动它
  8. hdu 1018 Big Number 数学结论
  9. Java 中 byte 类型初始化问题
  10. 【Mac + Appium + Python3.6学习(四)】之常用的IOS自动化测试API总结