请选择 进入手机版 | 继续访问电脑版

codeforces Good Bye 2020 D. 13th Labour of Heracles

[复制链接]
谢世民 发表于 2021-1-1 18:33:47 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
题目链接:https://codeforc.es/contest/1466/problem/D
outputstandard output
You’ve probably heard about the twelve labors of Heracles, but do you have any idea about the thirteenth? It is commonly assumed it took him a dozen years to complete the twelve feats, so on average, a year to accomplish every one of them. As time flows faster these days, you have minutes rather than months to solve this task. But will you manage?
In this problem, you are given a tree with n weighted vertices. A tree is a connected graph with n−1 edges.
Let us define its k-coloring as an assignment of k colors to the edges so that each edge has exactly one color assigned to it. Note that you don’t have to use all k colors.
A subgraph of color x consists of these edges from the original tree, which are assigned color x, and only those vertices that are adjacent to at least one such edge. So there are no vertices of degree 0 in such a subgraph.
The value of a connected component is the sum of weights of its vertices. Let us define the value of a subgraph as a maximum of values of its connected components. We will assume that the value of an empty subgraph equals 0.
There is also a value of a k-coloring, which equals the sum of values of subgraphs of all k colors. Given a tree, for each k from 1 to n−1 calculate the maximal value of a k-coloring.
Input
In the first line of input, there is a single integer t (1≤t≤105) denoting the number of test cases. Then t test cases follow.
First line of each test case contains a single integer n (2≤n≤105). The second line consists of n integers w1,w2,…,wn (0≤wi≤109), wi equals the weight of i-th vertex. In each of the following n−1 lines, there are two integers u, v (1≤u,v≤n) describing an edge between vertices u and v. It is guaranteed that these edges form a tree.
The sum of n in all test cases will not exceed 2⋅105.
Output
For every test case, your program should print one line containing n−1 integers separated with a single space. The i-th number in a line should be the maximal value of a i-coloring of the tree.
Example
input
  1. 443 5 4 62 13 14 3221 322 1620 13 17 13 13 112 13 14 15 16 1410 6 6 61 22 34 1
复制代码
output
  1. 18 22 255387 107 127 147 16728 38 44
复制代码
分析

每多一种颜色,就会有一个点的值会多加一次,设一个点的度为 x ,那么他的 w 最多会被加 x - 1 次,我们只要用优先队列维护这些值,从大到小加这些数,就能得到答案。
Happy new year !
代码

  1. #includeusing namespace std;typedef long long ll;const int N = 200007;int du[N];int w[N];priority_queue q;int main(){        int t;        scanf("%d",&t);        while(t--)        {                ll sum = 0;                while(!q.empty()) q.pop();                int n;                scanf("%d",&n);                for(int i=1;i 1) q.push(w[v]);                }                printf("%lld ",sum);                while(!q.empty())                {                        sum += q.top();                        q.pop();                        printf("%lld ",sum);                }                printf("\n");        }        return 0;}
复制代码
来源:https://blog.csdn.net/Sankkl1/article/details/112056639
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )