其实这道题不难
首先假设
1
1
1 是根节点
我看到这道题第一反应就是直接假设整棵树权值之和是某一个定值，然后再dfs造每一个
a
x
a_x
ax 。(其实到这里就可以a了，但是不优雅)
我们发现，由于去掉某一个节点之后，它所有的儿子所在的子树之和都和它上面那一部分之和是一样的，于是我们就有了：
s
u
m
x
′
s
s
o
n
=
s
u
m
1
−
s
u
m
x
sum_{x's\ son}=sum_1-sum_x
sumx′s son=sum1−sumx 其中(
x
≠
1
x\ne1
x=1，下同)
又因为：
a
x
=
s
u
m
x
−
∑
s
u
m
x
′
s
s
o
n
a_x=sum_x-\sum sum_{x's\ son}
ax=sumx−∑sumx′s son
结合一下就成了
a
x
=
s
u
m
1
−
d
e
g
x
×
(
s
u
m
1
−
s
u
m
x
)
a_x=sum_1-deg_x\times(sum_1-sum_x)
ax=sum1−degx×(sum1−sumx)
当我们令
s
u
m
1
=
0
sum_1=0
sum1=0 时，发现：
-
s
u
m
x
′
s
s
o
n
=
−
s
u
m
x
sum_{x's\ son}=-sum_x
sumx′s son=−sumx
-
a
x
=
d
e
g
x
∗
s
u
m
x
a_x=deg_x*sum_x
ax=degx∗sumx
我们再令
s
u
m
x
=
(
−
1
)
d
e
p
x
sum_x=(-1)^{dep_x}
sumx=(−1)depx ，就可以发现
a
x
=
d
e
g
x
(
−
1
)
d
e
p
x
a_x=deg_x(-1)^{dep_x}
ax=degx(−1)depx
不难发现，这个结论在
x
=
1
x=1
x=1 时也成立
再手动构造几组小数据后发现构造方法正确，就可以优雅的写代码了，芜湖起飞！
最后献上我其丑无比的代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,ans[N];
vector<int>ed[N];
void dfs(int x,int fa,int k){
ans[x]=ed[x].size()*k;
for(int y:ed[x])if(fa!=y)dfs(y,x,-k);
}
void solve(){
cin>>n;
for(int i=1;i<=n;i++)ed[i].clear();
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
ed[u].emplace_back(v);
ed[v].emplace_back(u);
}
dfs(1,1,1);
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
cout<<'\n';
}
int main(){
int t;
cin>>t;
while(t--)solve();
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
