题解：CF1280C Jeremy Bearimy

贪心是一种美学。

题意

有一棵有

2k

个结点的树，任意将它们分成

k

对，定义这棵树的路径和为每对结点之间的路径长度之和，分别求路径和的最小值和最大值。

Solution

先考虑最小值。考虑每条边的贡献，当一条边两边的结点数为奇数时，显然这条边必定要走至少一次。事实上将每条这样的边加入答案一次就是答案。

考虑这样做为什么对。如果一条边的两头都具有偶数个结点，就可以以这条边为界分成两个块，每个块内各自匹配，显然这样更优。

贪心地理解，如果两对点的路径有公共边，一定可以删掉这条公共边，交换匹配。

考虑最大值。我们有一种可能的做法，就是每次都取出树中一对距离最长的点（也就是树的直径）加入答案，并从树中删去这两个点，重复这个过程直到删完。不存在更优的解法。

注意到删到最后的点一定是树的重心，考虑从这点出发。显然树的直径必然经过重心，那么对于这一棵以重心为根的树，任何一个结点都可以走到根节点并与另外一棵子树内的一个结点匹配，那么一条边能产生的贡献就是它的权乘上它的子树内的结点数。

Code

CPP

#include<bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
const int N = 600005;
int t,k,n,u[N],v[N],w[N],dot,p[N],d[N],mmax[N];
struct node
{
	int v,w;
};
vector<node>vec[N];
void dfs(int u,int fa)
{
	p[u] = 1;
	mmax[u] = 0;
	for (node i: vec[u])
	{
		if (i.v != fa)
		{
			dfs(i.v,u);
			p[u] += p[i.v];
			mmax[u] = max(mmax[u],p[i.v]);
		}
	}
	if (mmax[u] <= n/2 && n-p[u] <= n/2) dot = u;
}
void dfs1(int u,int fa,int deep)
{
	d[u] = deep;
	p[u] = 1;
	for (node i: vec[u])
		if (i.v != fa)
			dfs1(i.v,u,deep+1),p[u] += p[i.v];
}
signed main()
{
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> t;
	while (t--)
	{
		cin >> k;
		n = k<<1;
		for (int i = 1; i <= n; i++)
			vec[i].clear();
		for (int i = 1; i < n; i++)
		{
			cin >> u[i] >> v[i] >> w[i];
			vec[u[i]].push_back({v[i],w[i]});
			vec[v[i]].push_back({u[i],w[i]});
		}
		dfs(1,1);
		dfs1(dot,dot,0);
		int ans1 = 0,ans2 = 0;
		for (int i = 1; i < n; i++)
		{
			if (d[u[i]] < d[v[i]]) swap(u[i],v[i]);
			if (p[u[i]]&1) ans1 += w[i];
			ans2 += p[u[i]]*w[i];
		}
		cout << ans1 << ' ' << ans2 << '\n';
	}
	return 0;
}

题解：CF1280C Jeremy Bearimy

文章操作

题意

Solution

Code

相关推荐

评论

题解：CF1280C Jeremy Bearimy