E – Equal Tree Sums CodeForces – 1656E
题目链接
题目：
给你一颗树，让你给树的每个顶点赋权值，使的去掉树上的任意一个点后，剩下的联通块的权值相等。
思路：
- 考虑二分染色，并且让每个顶点的权值和度数有关联。
-
可以 ： 对于黑色的顶点
uu
u
权值为
−d
e
g
(
u
)
-deg(u)
−
d
e
g
(
u
)
,白色v为
de
g
(
v
)
deg(v)
d
e
g
(
v
)
. -
考虑正确性：
[1]. 假设于
uu
u
相连的点有
vv
v
1
……
vv
v
p
，知道删除
uu
u
后这些点都不在一个连通块中(
因为是树形结构
)。
[2].再不妨假设u的权值为
+d
e
g
(
u
)
+deg(u)
+
d
e
g
(
u
)
,
vv
v
i
为
−d
e
g
(
v
-deg(v
−
d
e
g
(
v
i
))
)
(
:因为相邻
).
[3].我们知道对于一个连通块来说权值和为0. (有一条边相邻的顶点权值抵消)
[4].则会得到对于每一个连通块
vv
v
i
,
w(
v
w(v
w
(
v
i
)+
1
=
0
) + 1 = 0
)
+
1
=
0
(
因为只有和
uu
u
有一条临边。
ww
w
为
vv
v
i
连通块的点权值和
.这里假设的是
vv
v
的
de
g
deg
d
e
g
为负数，正数时是
w−
1
=
0
w-1=0
w
−
1
=
0
)
==> 可以推出
w(
v
w(v
w
(
v
i
)=
−
1
) = -1
)
=
−
1
,所有的连通块
vv
v
i
相等.
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5+10,M = 2e5+10;
int h[N],e[M],ne[M],idx;
void add(int a,int b)
{
ne[idx] = h[a],e[idx] = b,h[a] = idx++;
}
int deg[N],w[N];
int t,n;
void dfs(int u,int fa,int col){
w[u] = deg[u]*col;
for(int i = h[u];~i;i=ne[i]){
int y = e[i];
if(y == fa)continue;
dfs(y,u,col*-1);
}
}
void solve(){
cin >> n;
for(int i = 1,a,b;i<n;i++){
cin >> a >> b;
add(a,b),add(b,a);
deg[a] ++ ,deg[b] ++;
}
dfs(1,-1,-1);
for(int i = 1;i<=n;i++)cout << w[i] << " ";
cout << endl;
}
int main(){
cin >> t ;
while(t--){
memset(h,-1,sizeof h);
memset(deg,0,sizeof deg);
idx = 0;
solve();
}
return 0;
}