menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[思维]Codeforces700B【Connecting Universities】题解
apps Codeforces
local_offer 查看标签
comment 0 条评论

题目概述

一棵 $n$ 个点的树,给出 $2k$ 个关键点,现在要把这 $2k$ 个点组成 $k$ 对,每对的贡献为点之间的距离,求最大贡献。

解题报告

完全想不到……考虑每条边的贡献,很明显最大是第一个点子树中的关键点个数和第二个点子树中关键点的个数的最小值。但是每条边都能取到这个最大值吗?感性理解一下,用这样的方法进行构造,肯定是能够构造出来的。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=200000;

int n,K,cnt[maxn+5],X[maxn+5],Y[maxn+5];LL ans;
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x,int pre=-1){
    for (int j=lnk[x];j;j=nxt[j])
        if (son[j]!=pre) Dfs(son[j],x),cnt[x]+=cnt[son[j]];
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);for (int i=1,x;i<=(K<<1);i++) scanf("%d",&x),cnt[x]++;
    for (int i=1,x,y;i<n;i++) scanf("%d%d",&X[i],&Y[i]),Add(X[i],Y[i]),Add(Y[i],X[i]);Dfs(1);
    for (int i=1,MIN;i<n;i++) MIN=min(cnt[X[i]],cnt[Y[i]]),ans+=min(MIN,(K<<1)-MIN);
    return printf("%lld\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up