题解 单
Varuxn
·
·
个人记录
T2 单
解题思路
看遍网上题解都说是个高级的 换根DP 感觉有一点关系，但不知道也无妨。
先看暴力
暴力思路比较好像，对于t=1的情况直接Dij或者LCA，DFS也行；t=2的式子一看就可以高斯消元，要注意的就是卡一下精度，开double，输出的时候手动四舍五入或者加上一个1e-12也可以输出整数位，但是绝不能int强制转化！！！
code
再看正解
令sum[i]表示以 i 为根的子树的 a 之和。
t=0
可以得出式子：b[now]=(b[fa]-sum[now])+(sum[1]-sum[now])
以下图为例
假设now=6，那么 fa=4，将数值由fa转移到now
此时我们把整棵树划分为两部分：
现在，式子的前半部分就是fa的b减去now子树部分的a，这就是now子树对于b[now]的贡献以及B部分的部分贡献，相比于fa，now相较于B的深度多一，因此要加上sum[1]-sum[now]。这一块的式子很妙，可以多思考一下。
然后进行 DFS 求出 sum 数组，进而求出 b 数组就好了。
t=1
和t=1的式子有一定的关系，移一下项：
b[now]-b[fa]=sum[1]-sum[now]
求一下和：
\sum\limits_{i=2}^nb[i]+b[fa(i)]=sum[1]\times(n-1)-2\times\sum\limits_{i=2}^nsum[i]
也就是：
x_1b[1]+x_2b[2]+...+x_nb[n]=(n-1)sum[1]-2\times\sum\limits_{i=2}^nsum[now]
与前面的换根的思路相似，不难发现2\times\sum\limits_{i=2}^nsum[now]其实就是b[1],在此不做过多赘述。
然后进行DFS求出每个系数x，然后就可以求出sum[1]
再进行DFS求一下其他的sum。
然后再再进行DFS求出整棵树的a就好了。
## code
```cpp
#include<bits/stdc++.h>
#define int long long
//#define double long double
using namespace std;
const int N=1e5+10,M=1e4+10;
int T,n;
int dis[N],sum[N],s[N];
int tot,T_temp,head[N],nxt[N<<1],ver[N<<1],a[N],b[N];
inline void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs(int x,int fa,int dep)
{
b[1]+=a[x]*dep;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(to==fa)
continue;
dfs(to,x,dep+1);
}
}
void dfs1(int x,int fa)
{
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(to==fa)
continue;
dfs1(to,x);
sum[x]+=sum[to];
}
sum[x]+=a[x];
}
void dfs2(int x,int fa)
{
b[x]=b[fa]+sum[1]-2*sum[x];
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(to==fa)
continue;
dfs2(to,x);
}
}
inline void work_B()
{
dfs(1,0,0);
dfs1(1,0);
for(int i=head[1];i;i=nxt[i])
dfs2(ver[i],1);
for(int i=1;i<=n;i++)
printf("%lld ",b[i]);
printf("\n");
}
void dfs3(int x,int fa)
{
s[x]++;
s[fa]--;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(to==fa)
continue;
dfs3(to,x);
}
}
void dfs4(int x,int fa)
{
sum[x]=(b[fa]-b[x]+sum[1])/2;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(to==fa)
continue;
dfs4(to,x);
}
}
void dfs5(int x,int fa)
{
int temp=sum[x];
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i];
if(to==fa)
continue;
dfs5(to,x);
temp-=sum[to];
}
a[x]=temp;
}
inline void work_A()
{
memset(s,0,sizeof(s));
int temp=0;
for(int i=head[1];i;i=nxt[i])
dfs3(ver[i],1);
for(int i=1;i<=n;i++)
temp+=s[i]*b[i];
sum[1]=(temp+2*b[1])/(n-1);
for(int i=head[1];i;i=nxt[i])
dfs4(ver[i],1);
dfs5(1,0);
for(int i=1;i<=n;i++)
printf("%lld ",a[i]);
printf("\n");
}
inline void work()
{
tot=0;
memset(ver,0,sizeof(ver));
memset(head,0,sizeof(head));
memset(nxt,0,sizeof(nxt));
memset(sum,0,sizeof(sum));
scanf("%lld",&n);
for(int i=1,x,y;i<n;i++)
{
scanf("%lld%lld",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
scanf("%lld",&T_temp);
if(T_temp)
{
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
scanf("%lld",&b[i]);
work_A();
}
else
{
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
work_B();
}
}
#undef int
int main()
{
#define int register long long
#define ll long long
scanf("%lld",&T);
while(T--)
work();
return 0;
}
```