给定一棵带权树,一共有 (2k) 个点,求任意选择 (k) 对不重复点,每对点距离和的最小值与最大值
Solution
难度:L4
考虑最小:如果一条边的某一侧有奇数个点,那么很显然这条边一定会被选择。反之,这条边一定不会被选择,可从归纳角度考虑。因此,这个边集是完备的匹配边集合,每个边会被计算且只会被计算一次。于是,满足这个条件的边的总权值和就是最小答案。
考虑最大:延续上方的思路,我们发现,每条边被利用的最多次数是它所连接的两部分的点数的最小值,这个最大次数对于所有点来说可以同时达到。从另一种角度入手,我们希望每个点匹配到一个很远的点,以重心为根,那么每个点匹配的点一定不在原来的重心子树内,那么就很自然地将问题转化为了求重心为根时所有点的深度和。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
struct edge {int v,w;};
vector <edge> g[N];
int siz[N],vis[N],n,t1,t2,t3,ans1,ans2;
void dfs(int p) {
vis[p]=1;
siz[p]=1;
for(edge e:g[p]) {
int q=e.v, w=e.w;
if(vis[q]) continue;
dfs(q);
siz[p]+=siz[q];
if(siz[q]&1) ans1+=w;
ans2+=w*min(siz[q],n-siz[q]);
}
}
signed main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--) {
cin>>n;
n*=2;
for(int i=1;i<n;i++) {
cin>>t1>>t2>>t3;
g[t1].push_back({t2,t3});
g[t2].push_back({t1,t3});
}
dfs(1);
cout<<ans1<<" "<<ans2<<endl;
ans1=ans2=0;
memset(vis,0,sizeof vis);
memset(siz,0,sizeof siz);
for(int i=1;i<=n;i++) g[i].clear();
}
}