题目链接
题解链接

Time limit per test: 3.0 seconds
Memory limit: 256 megabytes

星光镇的地图是有 n 个点，n−1 条路，这些点从 1 到 n 编号，两两之间都可达；这 n−1 条路的长度都是 1。

这 n 个点是居民聚居点，第 i 个点上有 ai 个居民。去年的时候，星光镇政府曾经做了个人口普查，他们投入了大量的资金，获知了所有节点的 ai，而获知的目的，就是为新政府大楼的选址做准备的。由于新政府大楼一定会建在一个居民聚居点上，所以星光镇政府求出了对于每个聚居点 j 的「政府大楼收益评估函数」：

pj=∑i=1ndis(i,j)⋅ai
其中 dis(i,j) 是 i,j 号点之间的最短距离。特别的，dis(i,i)=0。

新政府大楼造好了，政府自然而然地进行了一些证据销毁工作，同时「一不小心」销毁了重金得来的人口普查数据：也就是说 ai 都丢失了。但是巧的是，所有的收益评估函数值 p1,p2,…,pn 竟然都留存了下来。星光镇数据研究所唐纳德博士表示：「从这些函数值中，我们完全可以将所有的人口数据都反求出来。」但是唐纳德博士，虽然是一个著名的数学天才，但却很有可能是一个假博士，他这话自然不能当真。所以当星光镇政府又要造一个新的政府大楼，又要用到这些人口数据时，他们花费了巨资进行再调查。

身在异国的你听到此事后大笑不止，利用 p1,p2,…,pn 轻轻松松地求出了 a1,a2,a3,…,an。

Input
输入具有如下形式：

nu1 v1⋮un−1 vn−1p1 p2 … pn−1 pn

第一行一个整数 n。

接下来 n−1 行，每行两个整数 ui,vi (1≤ui,vi≤n)，分别表示这 n−1 条路。这 n−1 条路都可以双向通行。两个居民聚居点之间不会有多条路相连，也不会有一条路的两端连接了同一个居民聚居点。

最后一行，用空格隔开的 n 个整数 p1,p2,…,pn，表示收益评估函数。

数据保证答案有解，并且满足 0≤a1,a2,…,an≤1 000。

数据规模约定：

对于 Easy 档：1≤n≤100。
对于 Hard 档：1≤n≤250 000。
Output
依次序输出 a1,a2,…,an。如果有多解，输出任意解。

Examples
input
2
1 2
11 9
output
9 11
input
6
1 2
1 3
3 4
3 5
5 6
32 45 19 28 16 21
output
0 1 2 3 4 5

题解：

Easy版本：

#include<bits/stdc++.h>
#define inf 0x3fffffff
using namespace std;
typedef long long ll;
int dis[105][105];
double eps=1e-3;
double a[105][105], del, f[105];
bool gauss(int n) {
    for (int i = 1; i <= n; i++) {
        int k = i;
        for (int j = i + 1; j <= n; j++)if (fabs(a[j][i]) > fabs(a[k][i]))k = j;
        if (fabs(del = a[k][i]) < eps)return 0;
        for (int j = i; j <= n + 1; j++)swap(a[i][j], a[k][j]);
        for (int j = i; j <= n + 1; j++)a[i][j] /= del;
        for (k = 1; k <= n; k++)if (k != i) {
            del = a[k][i];
            for (int j = i; j <= n + 1; j++)a[k][j] -= a[i][j] * del;
        }
    }
    return 1;
}

int p[1005];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i!=j)dis[i][j]=inf;
            else dis[i][j]=0;
        }
    int x,y;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        dis[x][y]=1;
        dis[y][x]=1;
    }
    for(int i=1;i<=n;i++)scanf("%d",&p[i]);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(i!=j&&j!=k&&k!=i)
                {
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
                }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)a[i][j]=dis[i][j];
        a[i][n+1]=p[i];
    }
    int flag=gauss(n);
    for(int i=1;i<=n;i++)
    {
        if(fabs(a[i][n+1])<=eps)printf("0");
        else printf("%.f",a[i][n+1]);
        if(i==n)printf("\n");
        else printf(" ");
    }
    return 0;
}
/* 6 1 2 1 3 3 4 3 5 5 6 32 45 19 28 16 21 */

其中高斯消元部分的代码模板
主要见大白书–即算法竞赛入门经典训练指南
该模板用的是高斯–约旦消元法，省略了回带部分，多了一部分时间，但代码简单

#include<bits/stdc++.h>
#define N 205
using namespace std;
const double eps=1e-8;
int n;
double a[N][N],del;
bool gauss(){
    for(int i=1;i<=n;i++){
        int k=i;
        for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[k][i]))k=j;
        if(fabs(del=a[k][i])<eps)return 0;
        for(int j=i;j<=n+1;j++)swap(a[i][j],a[k][j]);
        for(int j=i;j<=n+1;j++)a[i][j]/=del;
        for(k=1;k<=n;k++)if(k!=i){
            del=a[k][i];
            for(int j=i;j<=n+1;j++)a[k][j]-=a[i][j]*del;
        }
    }
    return 1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n+1;j++)scanf("%lf",&a[i][j]);
    bool flag=gauss();
    if(!flag)puts("No Solution");
    else for(int i=1;i<=n;i++)printf("%.2lf\n",a[i][n+1]);
    return 0;
}

PS
zzq wc-ctsc-apio-NOI Au；yql精通多项式；zyz精通女装；由乃精通数据结构；孔老师是毒奶大师；我没有学上：我们都有光明的前途。
https://www.cnblogs.com/zcysky/p/6946919.html
题目：
https://www.cnblogs.com/onioncyc/p/8137971.html
http://www.52ml.net/2698.html

复杂部分：
首先得弄懂p[i]数组的意思
我们不难留意到一个事实，对于一条边上的两个点，我们做一次减法，得到的就是这条边所连的两个连通块的和的差值。假设该树以 1 为根，我们记第 i 个节点的子树和与除了这个子树外其余节点的和的差为 ti，假如说我们知道整棵树的和 S，那么 S+ti 就是两倍的子树和（可以自行验证）。

这句话的理解看下面这张图，注意只有相邻的点才符合这个规则

可以验证一条边相连的两个点 ,相邻的两个点P[i]相减就正好等于第 i 个节点的子树和与除了这个子树外其余节点的和的差,

记第i个节点的子树和为sum1,其余点的和为sum2，S = sum1+sum2 ti = sum1-sum2 所以第i个节点的子树和正好是(S+ti)/2

关于这个

可以验证所有点(除了根1)的子树和加起来正好等于P1
而通过这个等式正好可以求出来S（需要先dfs求出所有的ti）

然后这样求出S，就可以求出所有点的子树和了
然后再dfs一遍所有的子树和减去重叠的部分就可以求出每个点的值了
code:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 3e5 + 10;

vector<int> g[N];
LL n, t[N], c[N], p[N], a[N];

void dfs(int u, int fa) {
    for (int v: g[u]) {
        if (v == fa) continue;
        t[v] = p[u] - p[v];
        dfs(v, u);
    }
}

void dfs2(int u, int fa) {
    for (int v: g[u]) {
        if (v == fa) continue;
        c[u] -= c[v];
        dfs2(v, u);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; ++i)
        cin >> p[i];
    dfs(1, 0);
    LL sum = 0;
    for (int i = 2; i <= n; ++i)
        sum += t[i];
    c[1] = sum = (2 * p[1] - sum) / (n - 1);
    for (int i = 2; i <= n; ++i)
        c[i] = (t[i] + sum) / 2;

    dfs2(1, 0);
    for (int i = 1; i <= n; ++i)
        printf("%lld%c", c[i], i == n ? '\n' : ' ');
    // for (int i = 1; i <= n; ++i)
    // printf("%d\n", t[i]);
    // printf("%d\n", sum);
}