T2192D. Cost of Tree

dp, greedy, trees, 1800, https://codeforces.com/problemset/problem/2192/D

For a tree 𝑇 with root 𝑟, where each node 𝑢 has a value 𝑎𝑢 associated with it, the cost of the tree defined as:

∑𝑢∈𝑇(𝑎𝑢⋅𝑑(𝑟,𝑢))

Here, this sum is taken over all nodes 𝑢 in the tree 𝑇, and 𝑑(𝑟,𝑢) denotes the number of edges on the shortest path from node 𝑟 to node 𝑢 on a tree.

You are given a tree consisting of 𝑛 nodes, rooted at node 1. Each node 𝑖 has a value 𝑎𝑖 assigned to it. For each 𝑟 from 1 to 𝑛, please solve the following problem independently:

Consider the subtree of node 𝑟 with respect to node 1. Formally, the subtree of node 𝑟 is the tree consisting of all nodes 𝑢 such that the shortest path from 1 to 𝑢 contains 𝑟.

Find the maximum cost of the subtree after performing at most one operation of the following type on the subtree:

Choose any node 𝑢 (𝑢≠𝑟). Remove the edge from 𝑢 to the parent of node 𝑢∗. Then, add an edge from 𝑢 to any node 𝑣 that is still reachable from 𝑟. It can be shown that after this operation, the graph remains a tree.

As an example, below shows an example of an operation with 𝑟=1,𝑢=5, and 𝑣=4.

∗Formally, remove the edge from 𝑢 to 𝑝, where 𝑝 is the unique node satisfying 𝑑(𝑢,𝑝)=1 and 𝑑(𝑢,𝑟)=𝑑(𝑝,𝑟)+1

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤104). The description of the test cases follows.

The first line of each testcase contains a single integer 𝑛 (1≤𝑛≤2⋅105) — the count of nodes in the tree.

The second line of each testcase contains 𝑛 integers 𝑎1,𝑎2,…,𝑎𝑛 (1≤𝑎𝑖≤2⋅105).

Then 𝑛−1 lines follow, the 𝑖-th line containing two integers 𝑢 and 𝑣 (1≤𝑢,𝑣≤𝑛) — the two nodes that the 𝑖-th edge connects.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of 𝑛 does not exceed 2⋅105 over all test cases.

Output

For each test case, print 𝑛 numbers – the answers for 𝑟=1,2,…,𝑛.

Example

input

3
5
1 3 2 1 2
1 2
2 3
3 4
3 5
7
1 2 3 1 3 2 1
1 2
2 3
3 4
4 5
4 6
3 7
5
5 4 3 2 1
1 2
2 3
3 4
4 5

output

18 10 5 0 0 
40 28 18 8 0 0 0 
20 10 4 1 0

Note

In the first test case, for 𝑟=1, it is optimal to choose 𝑢=5 and 𝑣=4. The cost of the tree is then 1⋅0+3⋅1+2⋅2+1⋅3+2⋅4=18. It can be shown that a larger cost cannot be obtained over all legal operations.

For 𝑟=4 for example, there is only 1 node in the subtree, so there is no operation possible. The only possible cost of the subtree is 0.

【江昊中数学科学学院】思路：

每个节点维护四个量 :

depth : 当前节点到子树中叶节点的最大距离
sum : 以当前节点为根的子树所有节点的 value 之和
cost : 不施加操作情况下, 子树的 cost
ans : 至多施加一次操作情况下, 子树的最大 cost
对于任意一个非叶节点 u , 想让一次操作后的 cost 尽可能大, 则只能是以下两种情况 :
在 u 的某个子节点 v 对应的子树内部进行操作, 这所带来的净增长是 ans[v] - cost[v]
将 u 的某个子节点 v 对应的子树整个移动到除 v 所在的分支之外，u 的其他分支中最深的那个叶子节点下面, 这所带来的净增长是 sum[v] * (d + 1)
代码

cpp

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

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    vector<int> value(n), depth(n);
    vector<ll> sum(n), cost(n), ans(n);
    for (int i = 0; i < n; i++) {
        cin >> value[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    auto dfs = [&](auto&& self, int u, int p) -> void {
        for (int v : adj[u]) {
            if (v == p) continue;
            self(self, v, u);
        }

        // 找到 u 的两个子树的最大深度 d1 和次大深度 d2
        int d1 = -1, d2 = -1;
        for (int v : adj[u]) {
            if (v == p) continue;
            if (depth[v] > d1) {
                d2 = d1;
                d1 = depth[v];
            } else if (depth[v] > d2) {
                d2 = depth[v];
            }
        }
        depth[u] = d1 + 1;

        sum[u] = value[u];
        for (int v : adj[u]) {
            if (v == p) continue;
            sum[u] += sum[v];
        }
        cost[u] = sum[u] - value[u];

        for (int v : adj[u]) {
            if (v == p) continue;
            cost[u] += cost[v];
        }

        for (int v : adj[u]) {
            if (v == p) continue;
            int d = (depth[v] == d1) ? d2 : d1;
            // ans[v] - cost[v] 代表操作在 v 的子树内部
            // sum[v] * (d + 1) 代表操作将 v 的整棵子树移动到其他的深度最大的子树下面
            ll tmp = max(ans[v] - cost[v], sum[v] * (d + 1));
            ans[u] = max(ans[u], tmp);
        }
        ans[u] += cost[u];
    };

    dfs(dfs, 0, -1);

    for (int i = 0; i < n; i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

T2192D. Cost of Tree ​

T2192D. Cost of Tree