题目大意：给定一棵树，令一个点到全部点的距离与点权的乘积之和为b[i]。求每一个点的权值a[i]

首先假设给定a[i]我们能够非常轻松的求出b[i] 可是反过来怎么搞？高斯消元？30W？

考虑已知a[i]求b[i]的情况 令这棵树的根为1 点i到根节点的距离为dis[i] 以i为根的子树的a值之和为size[i] 那么有递推式

b[1]=Σa[i]*dis[i]

b[x]=b[fa[x]]-2*size[x]+size[1]

将上式变形得：

2*size[x]=b[fa[x]]-b[x]+size[1]

且显然有

a[x]=size[x]-Σa[son[x]]

我们能够O(n)求出全部a[x]关于size[1]的一次函数关系 然后代入b[1]=Σa[i]*dis[i] 能够得到b[1]关于size[1]的一次函数关系 因为b[1]已知 所以size[1]就搞出来了

然后代入求出a[2]~a[n] 然后用size[1]减掉全部的a[2]~a[n]就是a[1]

别忘了开long long

多解啥的 看到没有Special Judge就知道 那是逗你的……

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 300300

using namespace std;

typedef long long ll;

typedef pair<ll,ll> abcd;

struct edge{

	int to,next;

}table[M<<1];

int head[M],tot;

int n,ans,fa[M],dis[M];

ll a[M],b[M];

abcd double_size[M],double_a[M],b_1;

void Add(int x,int y)

{

	table[++tot].to=y;

	table[tot].next=head[x];

	head[x]=tot;

}

abcd operator += (abcd &x,const abcd &y)

{

	x.first+=y.first;

	x.second+=y.second;

}

void operator -= (abcd &x,const abcd &y)

{

	x.first-=y.first;

	x.second-=y.second;

}

abcd operator * (const abcd &x,int y)

{

	return abcd( x.first * y , x.second * y );

}

void BFS()

{

	static int q[M],r,h;

	int i;

	q[++r]=1;

	while(r!=h)

	{

		int x=q[++h];

		for(i=head[x];i;i=table[i].next)

			if(table[i].to!=fa[x])

			{

				fa[table[i].to]=x;

				dis[table[i].to]=dis[x]+1;

				q[++r]=table[i].to;

			}

	}

}

int main()

{

	int i,x,y;

	cin>>n;

	for(i=1;i<n;i++)

		scanf("%d%d",&x,&y),Add(x,y),Add(y,x);

	for(i=1;i<=n;i++)

		scanf("%d",&b[i]);

	BFS();

	for(i=2;i<=n;i++)

		double_size[i]=abcd(1,b[fa[i]]-b[i]);

	for(x=2;x<=n;x++)

	{

		double_a[x]=double_size[x];

		for(i=head[x];i;i=table[i].next)

			if(table[i].to!=fa[x])

				double_a[x]-=double_size[table[i].to];

		b_1+=double_a[x]*dis[x];

	}

	ans=(b[1]+b[1]-b_1.second)/b_1.first;

	a[1]=ans;

	for(i=2;i<=n;i++)

	{

		a[i]=double_a[i].first*ans+double_a[i].second>>1;

		a[1]-=a[i];

	}

	for(i=1;i<=n;i++)

		printf("%lld%c",a[i],i==n?'\n':' ');

}

+