CodeTON Round 1 E. Equal Tree Sums

传送门

题目大意

一棵 \(n(3\leq n\leq 10^5)\) 个节点的无根树，为每个节点 \(i\) 赋予一个权值 \(a_i(-10^5\leq a_i\leq 10^5,a_i\neq 0)\) ，使得在删去任意一个节点后，剩下的各个连通块的权值和都相等。

思路

我们对这棵树做二分图染色，一部分的节点赋予 \(deg_v\) 的权值，另一部分的节点赋予 \(-deg_v\) 的权值，这样在删去某个顶点 \(u\) 后，连通块中所有不与 \(u\) 相连的边会为该连通块权值的总和贡献一个 \(1\) 和一个 \(-1\) ，总的贡献为 \(0\) ，而该连通块与 \(u\) 的连边对总和的贡献取决于 \(w_u\) 的正负性，于是删去 \(u\) 后各个连通块的权值和就都相等了。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 100000000;
const LL mod = 998244353;
const int maxn = 200010;

vectorG[maxn];
int T, N;
int ans[maxn];

void add_edge(int from, int to)
{
	G[from].push_back(to);
	G[to].push_back(from);
}

void dfs(int v, int p, int t)
{
	if (!t)
		ans[v] = -ans[v];
	for (auto to : G[v])
	{
		if (to == p)
			continue;
		dfs(to, v, t ^ 1);
	}
}

void solve()
{
	dfs(1, 0, 0);
	for (int i = 1; i <= N; i++)
		cout << ans[i] << ' ';
	cout << endl;
}

int main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		cin >> N;
		for (int i = 1; i <= N; i++)
			G[i].clear(), ans[i] = 0;
		int u, v;
		for (int i = 1; i < N; i++)
		{
			cin >> u >> v;
			add_edge(u, v);
			ans[u]++, ans[v]++;
		}
		solve();
	}

	return 0;
}