专栏文章

题解：P9305 「DTOI-5」校门外的枯树

细细数繁星
P9305题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@ming8e8k
此快照首次捕获于
2025/12/02 01:54
3 个月前
此快照最后确认于
2025/12/02 01:54
3 个月前
查看原文
额，事实上我自己做出来的部分只有 41 分，是某大佬指点迷津才 AC 的。
kk 只有两种取值：11 与 22。考虑分类讨论。
设 MiM_i 表示以 ii 为根节点的字数的重量。

k=1k=1

这部分相当好拿分。先预处理 MiM_i。
链 1∼i1\sim i 的左边部分的重量和右边部分的重量是容易处理的。这样 k=1k=1 就做出来了啦。答案就是重量差的最小值。贴代码：
CPP
#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int k;
const int N = 1E5 + 5;
vct<pair<int ,int> > E[N];
bool yz[N];
int m[N], lef[N], rig[N];

void dfs(int u, int fa) {
	int sum = 0;	
	int tmpsum = 0;
	for (auto tmp : E[u]) {
		int v = tmp.first, w = tmp.second;
		if (v == fa) continue;
		sum += w + m[v];
	}
	for (auto tmp : E[u]) {
		int v = tmp.first, w = tmp.second;
		if (v == fa) continue;
		yz[u] = 1;
		int p0 = tmpsum, p1 = sum - tmpsum - m[v] - w;
		lef[v] = lef[u] + p0, rig[v] = rig[u] + p1;
		tmpsum += m[v] + w;
		dfs(v, u);
	}
}

void dfs_firs(int u, int fa) {
	for (auto tmp : E[u]) {
		int v = tmp.first, w = tmp.second;
		if (v == fa) continue;
		dfs_firs(v, u);
	}
	for (auto tmp : E[u]) {
		int v = tmp.first, w = tmp.second;
		if (v == fa) continue;
		m[u] = m[u] + m[v] + w;
	}
}

void solve() {
	memset(yz, 0, sizeof yz);
	int n;
	cin >> n;
	rep(i, 1, n) {
		E[i].clear();
		m[i] = 0;
	}
	rep(i, 1, n) {
		int x;
		cin >> x;
		rep(j, 1, x) {
			int v, w;
			cin >> v >> w;
			E[i].push_back({v, w});
		}
	}
	dfs_firs(1, 0);
	dfs(1, 0);
	if (k == 1) {
		int ans = 2e9;
		rep(i ,1, n) {
			if (!yz[i])
				ans = min(ans, abs(lef[i] - rig[i]));
		}
		cout << ans << '\n';
	} 
}


main() {
	int t; cin >> t >> k; while (t--) solve();
	
	return 0;
}

k=2k=2

其实 k=1k=1 做完了 k=2k=2 也很好想，鄙人大脑完全不发育竟然没想到。
取所有的叶子结点，注意到因为同一层的结点 MiM_i 单调递增。可以二分叶子结点，完成 k=2k=2 的部分。
接下来我们换一种处理方式：
  • LiL_i，表示按顺序搜索到 ii 时所经过的边的权值和。
  • SiS_i，表示链 1∼i1\sim i 的重量。
  • MiM_i，表示以 ii 为根节点的子树的重量。
则对于以 ii 为根节点的树中，链 i∼ji\sim j 的重量就是 Sj−SiS_j-S_i，链 i∼ji\sim j 的重量与其左侧部分的重量之和就是 Lj−LiL_j-L_i。
加个二分优化，就做完了。
代码：
CPP
#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int k;
const int N = 1E5 + 5;
vct<pair<int ,int> > E[N];
int m[N], lef[N], dfn_mx[N], dfn_mn[N], cnt, dfn_belonged[N], chain_sum[N];

void dfs_firs(int u) {
	dfn_mn[u] = cnt;
	for (auto tmp : E[u]) {
		int v = tmp.first, w = tmp.second;
		chain_sum[v] = chain_sum[u] + w;
		dfs_firs(v);
		m[u] = m[u] + m[v] + w;
	}
	if (!E[u].size()) {
		++cnt;
		dfn_belonged[cnt] = u;
	}
	dfn_mx[u] = cnt;
}

void dfs_seco(int u) {
	int sum = 0;
	for (auto tmp : E[u]) {
		int v = tmp.first, w = tmp.second;
		lef[v] = lef[u] + sum + w;
		dfs_seco(v);
		sum += m[v] + w;
	}
}

int query(int from, int to) {
	int wei_chain = chain_sum[to] - chain_sum[from];
	int left = lef[to] - lef[from] - wei_chain;
	return left - (m[from] - left - wei_chain);
}

void solve() {
	memset(dfn_belonged, 0, sizeof dfn_belonged);
	memset(dfn_mx, 0, sizeof dfn_mx);
	memset(dfn_mn, 0, sizeof dfn_mn);
	memset(lef, 0, sizeof lef);
	memset(m, 0, sizeof m);
	memset(chain_sum, 0, sizeof chain_sum);
	lef[1] = chain_sum[1] = 0;
	cnt = 0;
	int n;
	cin >> n;
	rep(i, 1, n) {
		E[i].clear();
		m[i] = 0;
	}
	rep(i, 1, n) {
		int x;
		cin >> x;
		rep(j, 1, x) {
			int v, w;
			cin >> v >> w;
			E[i].push_back({v, w});
		}
	}
	dfs_firs(1);
	dfs_seco(1);
	// cout << chain_sum[5];
	rep(i, 1, n) {
		if (k == 1 && i != 1) {
			continue;
		}
		int l = dfn_mn[i], r = dfn_mx[i];
		while (l + 1 < r) {
			int mid = (l + r) / 2;
			if (query(i, dfn_belonged[mid]) >= 0) {
				r = mid;
			} else l = mid;
		}
		cout << min(abs(query(i, dfn_belonged[l])), abs(query(i, dfn_belonged[r]))) << ' ';
	}
	cout << '\n';
}


main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t >> k; while (t--) solve();
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...