meepo's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

Source

    这道题真的是太神了。。。

    刚开始看到有多组解以为是构造可行解。。然后在那里想贪心什么的可不可以做。。然后突然发现这题没有SPJ。。。。 出题人你这坑挖的有点大啊。。

    后来实在想不出去看了PoPoQQQ的blog。。。感觉实在是太神了、。、、

    我们可以先想怎么通过a[i]计算b[i]。。

    这个可以用树形DP做。。设1为根.dis[x]为x到根的距离.size[x]为以x为根的子树的权值和。。\[b[1] = \Sigma a[i]*dis[i]\]\[b[x] = b[fa[x]]-size[x]+(size[1]-size[x])\]\[=b[fa[x]]-2*size[x]+size[1]\]所以可以得到\[2*size[x]=b[fa[x]]-b[x]+size[1]\]显然的\[a[x] = size[x]-\Sigma a[son[x]]\]

    因为我们知道了所有的b[i]。所以我么可以根据\(2*size[x]=b[fa[x]]-b[x]+size[1]\)求出\(2*size[i]-size[1]=b[fa[i]]-b[i]\)。。我们把这个设为doublesize

    然后根据\(a[x] = size[x]-\Sigma a[son[x]]\)可以类似的求出\(doublea[i] = doublesize[i]-\Sigma doublesize[x](x为i的儿子节点)\)

    但是我们求出的这些值中都带有size[1]。。所以我们要把这些消掉。。因为我们知道\(b[1] = \Sigma a[i]*dis[i]\)我们同理合并所有的doublea得到doubleb1然后因为b[1]已知所以我们可以求出size[1]的值。。然后就可以把所有doublea中的size[1]去掉求出a[i]。。。然后一切就完美地解决了。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
const ll N = 300010;
struct data{ll first,second;} double_a[N],double_size[N],b_1;
struct node{ll x,y,next;} e[N<<1];
ll head[N],b[N],a[N],n,cnt,x,y,ans,h,t,q[N],dis[N],fa[N];
ll read(){
	ll x = 0,f = 1,c = getchar();
	while (c<'0' || c>'9') {if (c=='-') f = -1;c = getchar();}
	while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
	return x*f;
}
void Insert(ll x,ll y){
	e[++cnt].x = x;e[cnt].y = y;
	e[cnt].next = head[x];head[x] = cnt;
}
void operator -= (data &a,data b){a.first-=b.first;a.second-=b.second;}
void operator += (data &a,data b){a.first+=b.first;a.second+=b.second;}
data operator * (data a,ll b){return (data){a.first*b,a.second*b};}
void Bfs(){
	q[1] = 1;h = 0;t = 1;
	while (h<t){
		ll x = q[++h];
		for (ll i=head[x];i;i=e[i].next)
			if (e[i].y !=fa[x]){
				fa[e[i].y] = x;
				dis[e[i].y] = dis[x]+1;
				q[++t] = e[i].y;
			}
	}
}
int main(){
	n = read();
	for (ll i=1;i<n;i++){
		x = read();y = read();
		Insert(x,y);Insert(y,x);
	}
	for (ll i=1;i<=n;i++) b[i] = read();
	Bfs();
	for (ll i=2;i<=n;i++) double_size[i] = (data){1,b[fa[i]]-b[i]};
	for (ll x=2;x<=n;x++){
		double_a[x] = double_size[x];
		for (ll i=head[x];i;i=e[i].next)
			if (e[i].y!=fa[x]) double_a[x]-=double_size[e[i].y];
		b_1+=double_a[x]*dis[x];
	}
	ans = a[1] = (2*b[1]-b_1.second)/b_1.first;
	for (ll i=2;i<=n;i++){a[i] = (double_a[i].second+double_a[i].first*ans)/2;a[1]-=a[i];}
	for (ll i=1;i<n;i++) printf("%lld ",a[i]);printf("%lld\n",a[n]);
}