首页 > 代码库 > 【CF700B】Connecting Universities（想法题，贪心，树上最短路）
【CF700B】Connecting Universities（想法题，贪心，树上最短路）
题意：给出一棵树上的2*k个节点，给他们配对，使得他们之间的距离和最大。
思路：一条边的两侧如果有一侧没有给定的节点就不会被经过……
如果有1个节点就会被经过1次……
如果两侧分别有x,y个给定节点就会被经过min(x,y)次
因为要使总路程最大就是让每一条路被走过最多的次数
肯定是两侧各取一个 剩下的只能在某侧内部解决
所以按此统计即可
答案很大 用INT64
1 var head,vet,next,a,b,c,dep,flag,f:array[1..500000]of longint; 2 n,k,tot,i:longint; 3 ans:int64; 4 5 procedure add(a,b:longint); 6 begin 7 inc(tot); 8 next[tot]:=head[a]; 9 vet[tot]:=b;10 head[a]:=tot;11 end;12 13 function min(x,y:longint):longint;14 begin15 if x<y then exit(x);16 exit(y);17 end;18 19 procedure dfs(u,fa:longint);20 var e,v:longint;21 begin22 flag[u]:=1;23 e:=head[u];24 while e<>0 do25 begin26 v:=vet[e];27 if (v<>fa)and(flag[v]=0) then28 begin29 dep[v]:=dep[u]+1;30 dfs(v,u);31 f[u]:=f[u]+f[v];32 end;33 e:=next[e];34 end;35 end;36 37 begin38 read(n,k);39 for i:=1 to 2*k do40 begin41 read(c[i]);42 f[c[i]]:=1;43 end;44 for i:=1 to n-1 do45 begin46 read(a[i],b[i]);47 add(a[i],b[i]);48 add(b[i],a[i]);49 end;50 dfs(1,-1);51 for i:=1 to n-1 do52 if dep[a[i]]>dep[b[i]] then ans:=ans+min(f[a[i]],2*k-f[a[i]])53 else ans:=ans+min(f[b[i]],2*k-f[b[i]]);54 writeln(ans);55 56 end.
【CF700B】Connecting Universities（想法题，贪心，树上最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。