[cf] CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes) E. Equal Tree Sums 黑白染色思想

前言

传送门 : u1s1,在被D题搞傻的情况下开了E，以为是 D P DP DP结果一点想法都没有

思路

我们考虑将每个点的度数 想象为 对当前点的贡献

我们考虑黑白染色 , 这样子整个图的总和为 0 0 0

当我们删除一个度数为 k k k的点的时候,显然被分为了 k k k个集合

而每个集合的总和都为 − 1 -1 −1,因为相当于每个集合都删除了一条边,使得贡献 − 1 -1 −1

没想到 黑白染色思想这么有用,记得上次见到黑白染色还是在基础课 下面还有两题也是黑白染色待补了 : 1.nk Treepath 2.cf 383C :Propagating tree

Mycode

const int N  = 1e5+10;
int ans[N];

void dfs(int u,int fa,int c,vector g[]){
	ans[u] = c * g[u].size();
	for(auto x : g[u]){
		if(x!=fa)
		dfs(x,u,-c,g);
	}
}
void solve()
{
	int n;cin>>n;
	vector g[n+1];
	
	for(int i=1;i>x>>y;
		g[x].pb(y);
		g[y].pb(x);
	}
	
	dfs(1,1,1,g);
	for(int i=1;i