Codeforces - 1656E - Equal Tree Sums（构造 + 树论 + 图论 + 搜索、结论题、*2200）

1656E - Equal Tree Sums（⇔源地址）

• 1656E - Equal Tree Sums（⇔源地址）
  • tag
  • 题意
  • 思路
  • AC代码
  • 错误次数：0

tag

⇔*2200、⇔构造、⇔树论、⇔图论、⇔搜索、⇔结论题

题意

给定一个包含 \(N\) 个节点的无根树。请给这棵树上的每个点赋一个绝对值不超过 \(10^5\) 的非零权值，使得当树上任意一个节点被移除时，所有连通块的点权和相等。

思路

首先，这里有一个结论，即将树进行黑白染色，对于黑色点 \(x\) ，其点权为 1 * deg[x] ；对于白色点 \(y\) ，其点权为 -1 * deg[x] 。**这样操作过后，整棵树的点权和为 \(0\) **。

证明如下：

对于一条边 \((x,y)\) ，\(x,y\) 的颜色相反，假设 \(x\) 为白色，那么这一条边会给 \(x\) 贡献 \(1\) ，会给 \(y\) 贡献 \(-1\) ，恰好抵消。这一论证对于所有的边均成立，故点权和为 \(0\) 。

可以证明，这样的赋值方式同时能够满足题意，证明如下。

假设树上某个节点 \(x\) 被移除后，所有节点的点权值可以改变，我们发现，改变的点均为 \(x\) 的父亲节点或是孩子节点，改变的值为 \(1\) 或 \(-1\) ，符号与 \(x\) 的颜色相关。改变后，所有连通块的点权和依旧相等，且为 \(0\) 。

再考虑点 \(x\) 移除后锁头节点的点权值不能发生改变，我们发现，这一操作对所有连通块点权和的贡献是相等的，均为 \(1\) 或 \(-1\) ，符号与 \(x\) 的颜色相关。

AC代码

namespace G {
	vector<int> ver[N];
	int deg[N], ans[N], vis[N];
	
	void clear(int n) {
		for (int i = 1; i <= n; ++ i) {
			ver[i].clear();
			deg[i] = vis[i] = ans[i] = 0;
		}
	}
	void add(int x, int y) {
		ver[x].push_back(y);
		++ deg[y];
	}
	void dfs(int x, int p) {
		vis[x] = 1;
		if (p) ans[x] = deg[x];
		else ans[x] = -deg[x];
		for (auto y : ver[x]) {
			if (vis[y]) continue;
			dfs(y, 1 - p);
		}
	}
	void solve(int n) {
		dfs(1, 1);
		for (int i = 1; i <= n; ++ i) cout << ans[i] << " ";
		cout << endl;
	}
}
bool Solve() {
	int n; cin >> n;
	for (int i = 1, x, y; i < n; ++ i) {
		cin >> x >> y;
		G::add(x, y), G::add(y, x);
	}
	G::solve(n);
	G::clear(n);
	return 0;
}

错误次数：0

文 / WIDA
2023.01.07 成文
首发于WIDA个人博客，仅供学习讨论