晚間測試3 B. 單(single)
題目描述
單車聯通大街小巷.這就是出題人沒有寫題目背景的原因.
對於一棵樹,認為每條邊長度為 \(1\),每個點有一個權值\(a[i]\).\(dis(u,v)\)為點\(u\)到\(v\)的最短路徑的邊數.\(dis(u,u)=0\).對每個點求出一個重要程度.點\(x\)的重要程度\(b[x]\)定義為其他點到這個點的距離乘上對應的點權再求和. 即:\(b[x]=a[1]*dis(1,x)+a[2]*dis(2,x)+….+a[n]*dis(n,x)\)
現在有很多樹和對應的\(a\)數組，並求出了\(b\)數組.不幸的是，記錄變得模糊不清了.幸運的是,樹的形態完好地保存了下來,\(a\)數組和\(b\)數組至少有一個是完好無損的,但另一個數組完全看不清了.
希望你求出受損的數組.多組數據.
輸入格式
第一行輸入一個\(T\)，表示數據組數。接下來\(T\)組數據。
每組數據的第\(1\)行\(1\)個整數\(n\)表示樹的點數.節點從\(1\)到\(n\)編號.
接下來\(n-1\)行每行兩個整數\(u,v\)表示\(u\)和\(v\)之間有一條邊.
接下來一行一個整數\(t\)，表示接下來數組的類型。
\(t=0\)則下一行是\(a\)數組，\(t=1\)則下一行是\(b\)數組。
接下來一行\(n\)個整數，表示保存完好的那個數組，第\(i\)個數表示\(a[i]\)或\(b[i]\)。
輸出格式
\(T\)行，每組數據輸出一行表示對應的\(a\)數組或\(b\)數組，數組的相鄰元素用一個空格隔開。忽略行末空格和行尾回車.
樣例
樣例輸入
2
2
1 2
1
17 31
2
1 2
0
31 17
樣例輸出
31 17
17 31
數據範圍與提示
對於\(100\%\)的數據，\(T=5,2<=n<=100000,1<=u,v<=n\),保證給出的\(n-1\)條邊形成一棵樹
對於\(100\%\)的數據，\(t=0\)或\(t=1,1<=a[i]<=100,1<=b[i]<=10^9\)，\(t=1\)時保證給出的\(b\)數組對應唯一的一個\(a\)數組。
對於\(100\%\)的數據，單個輸入文件不會包含超過\(2000000\)個整數，這段話可以理解為，你不必考慮輸入輸出對程式運行時間的影響。
對於\(100\%\)的數據，保證答案不會超過\(int\)能表示的範圍
接下來的表格中描述了每個測試點的具體特徵。每個測試點的\(5\)組數據均符合表格中對應的特徵。
分析
默認 \(1\) 號節點為根節點
我們設 \(sum[i]\) 為以 \(i\) 為根的子樹中 \(a\) 數組的和
當 \(t=0\) 時，顯然是一個換根 \(DP\)，有 \(b[now]=b[fa]+sum[1]-sum[now]-sum[now]\)
當 \(t \neq 0\) 時，如果數據範圍較小的話可以進行高斯消元
但是這道題的 \(n\) 比較大，所以我們只能推式子
由換根 \(DP\) 的式子，我們可以得到對於除\(1\)之外的任何節點都有 \(b[now]-b[fa]=sum[1]-2sum[now]\)
我們把這些式子相加，可以得到 \(x_1b[1]+x_2b[2]+…+x_nb[n]=(n-1)sum[1]-2 \sum_{i=2}^nsum[now]\)
對於左邊這一堆，我們可以 \(dfs\) 求出每一個節點對應的係數 \(x_i\)，從而得到左邊的值
對於右邊的 \(\sum_{i=2}^nsum[now]\)，其實就是 \(b[1]\)
因為我們在換根 \(DP\) 的第一個 \(dfs\) 時會有 \(b[1]= \sum_{u=son\ of\ 1}sum[u]+g[u]\)
其中 \(g[u]=\sum_{v=son\ of\ u}sum[v]+g[v]\)
當遞歸到葉子節點時，會有\(g[u]=sum[u]=a[u]\)
所以\(\sum_{i=2}^nsum[now]=b[1]\)
我們帶入上面的式子就可以求出 \(sum[1]\)
進行一遍 \(dfs\) 可以求出所有節點的\(sum\)值
再進行一遍 \(dfs\) 就可以求出所有節點的\(a\)值
程式碼
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define int long long
inline int read(){
int x=0,fh=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int n,head[maxn],tot=1,t;
struct asd{
int to,next;
}b[maxn];
void ad(int aa,int bb){
b[tot].to=bb;
b[tot].next=head[aa];
head[aa]=tot++;
}
void clr(){
memset(head,-1,sizeof(head));
memset(&b,0,sizeof(b));
tot=1;
}
int zd[maxn];
int f[maxn],g[maxn],siz[maxn],sum;
void dfs1(int now,int fa){
siz[now]=zd[now];
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==fa) continue;
dfs1(u,now);
g[now]+=g[u]+siz[u];
siz[now]+=siz[u];
}
}
void dfs2(int now,int fa){
if(now==1){
f[now]=g[now];
}
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==fa) continue;
f[u]=f[now]+sum-siz[u]-siz[u];
dfs2(u,now);
}
}
void solve1(){
memset(siz,0,sizeof(siz));
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));
sum=0;
for(int i=1;i<=n;i++){
sum+=zd[i];
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++){
printf("%lld ",f[i]);
}
printf("\n");
}
int nans,ncnt,xs[maxn];
void dfs3(int now,int fa){
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==fa) continue;
dfs3(u,now);
xs[u]++;
xs[now]--;
}
}
void dfs4(int now,int fa){
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==fa) continue;
siz[u]=(siz[1]+zd[now]-zd[u])/2;
dfs4(u,now);
}
}
void dfs5(int now,int fa){
for(int i=head[now];i!=-1;i=b[i].next){
int u=b[i].to;
if(u==fa) continue;
siz[now]-=siz[u];
dfs5(u,now);
}
}
void solve2(){
memset(siz,0,sizeof(siz));
memset(xs,0,sizeof(xs));
dfs3(1,0);
nans=0;
for(int i=1;i<=n;i++){
nans+=(1LL*zd[i]*xs[i]);
}
siz[1]=nans-ncnt*zd[1];
siz[1]+=2*zd[1];
siz[1]/=(n-1);
dfs4(1,0);
dfs5(1,0);
for(int i=1;i<=n;i++){
printf("%lld ",siz[i]);
}
printf("\n");
}
signed main(){
freopen("single.in","r",stdin);
freopen("single.out","w",stdout);
t=read();
while(t--){
clr();
n=read();
int aa,bb,op;
for(int i=1;i<n;i++){
aa=read(),bb=read();
ad(aa,bb);
ad(bb,aa);
}
op=read();
for(int i=1;i<=n;i++){
zd[i]=read();
}
if(op==0){
solve1();
} else {
solve2();
}
}
return 0;
}
